hdu 4768 Flyer 二分

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<set>
 7 #include<vector>
 8 #define ll long long
 9 #define M 200005
10 #define inf 1e20
11 #define mod 1000000007
12 using namespace std;
13 struct inter
14 {
15     ll a,b,c;
16 }p[M];
17 bool cal(int n)
18 {
19     ll ans=0;
20     for(int i=0;i<n;i++)
21         ans+=(p[i].b-p[i].a)/p[i].c+1;
22     return ans&1;
23 }
24 int main()
25 {
26     int i,j,k,m,n,x;
27     ll l,r,mid;
28     while(scanf("%d",&n)!=EOF){
29         l=inf;r=0;
30         for(i=0;i<n;i++){
31             scanf("%I64d%I64d%I64d",&p[i].a,&p[i].b,&p[i].c);
32             l=min(l,p[i].a);
33             r=max(r,p[i].b);
34         }
35         if(!cal(n)){
36             printf("DC Qiang is unhappy.
");
37             continue;
38         }
39         while(l<=r){
40             mid=(l+r)>>1;
41             ll ret=0;
42             for(i=0;i<n;i++){
43                 if(mid<p[i].a) continue;
44                 ll rr=min(mid,p[i].b);
45                 ret+=(rr-p[i].a)/p[i].c+1;
46             }
47             if(ret&1) m=mid,r=mid-1;
48             else l=mid+1;
49         }
50         int ans=0;
51         for(i=0;i<n;i++)
52             if(m>=p[i].a&&m<=p[i].b&&(m-p[i].a)%p[i].c==0)
53                 ans++;
54         printf("%d %d
",m,ans);
55     }
56     return 0;
57 }