AcWing 120. 防线
原题链接
中等
作者:
徐学神
,
2024-04-23 17:53:15
,
所有人可见
,
阅读 3
求赞!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=200010;
ll t,n,s[N],e[N],d[N];
ll get(ll x) {
ll cnt=0;
for(ll i=1; i<=n; i++) if(s[i]<=x) cnt+=(min(x,e[i])-s[i])/d[i]+1;
return cnt;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--) {
ll l=0,r=0;
cin>>n;
for(ll i=1; i<=n; i++) {
cin>>s[i]>>e[i]>>d[i];
r=max(r,e[i]);
}
while(l<r) {
ll mid=(l+r)>>1;
if(get(mid)&1) r=mid;
else l=mid+1;
}
ll sum=get(l)-get(l-1);
if(sum&1) cout<<l<<" "<<sum<<"\n";
else cout<<"There's no weakness.\n";
}
return 0;
}