【题解】Luogu P4403 [BJWC2008] 秦腾与教学评估

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 namespace gengyf{
 4 #define ll long long
 5 const int maxn=2e5+10;
 6 inline ll read(){
 7     ll x=0,f=1;
 8     char c=getchar();
 9     while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
10     while(c>=‘0‘&&c<=‘9‘){x=(x*10)+c-‘0‘;c=getchar();}
11     return x*f;
12 }
13 int T,n,ans;
14 ll s[maxn],e[maxn],d[maxn];
15 bool fl;
16 ll check(ll pos){
17     ll tmp=0;
18     for(int i=1;i<=n;i++){
19         if(s[i]<=pos){
20             tmp+=(min(pos,e[i])-s[i])/d[i]+1;
21         }
22     }
23     return tmp;
24 }
25 int main(){
26     T=read();
27     while(T--){
28         n=read();ll l=0,r=0;ans=0;
29         for(int i=1;i<=n;i++){
30             s[i]=read();e[i]=read();d[i]=read();
31             r=max(r,e[i]);
32         }
33         if(check(r)%2==0){
34             puts("Poor QIN Teng:(");
35             continue;
36         }
37         while(l<r){
38             ll mid=(l+r)>>1;
39             if(check(mid)%2==1)r=mid;
40             else l=mid+1;
41         }
42         for(int i=1;i<=n;i++){
43             if(s[i]>l||e[i]<l)continue;
44             if((l-s[i])%d[i]==0)ans++;
45         }
46         printf("%lld %d\n",l,ans);
47     }
48     return 0;
49 }
50 }
51 signed main(){
52   gengyf::main();
53   return 0;
54 }