hdu 4768 Flyer (二分)

FlyerTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 631 Accepted Submission(s): 220

Problem DescriptionInputOutputSample InputSample OutputSource#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>//#pragma comment (linker,"/STACK:102400000,102400000")#define maxn 20005#define mod 1000000000#define INF 0x3f3f3f3fusing namespace std;typedef __int64 ll;ll n,m,ans,flag;ll id,cnt,mi,ma;struct Node{ ll a,b,c;} pp[maxn];ll calnum(ll le,ll ri){ ll i,j,t,tl,tr,sum=0; for(j=1; j<=n; j++) { tl=max(pp[j].a,le); tr=min(pp[j].b,ri); if(tl>tr||tr<pp[j].a||tl>pp[j].b) continue ; sum=sum+(tr-(pp[j].a-pp[j].c))/pp[j].c-max(0LL,(tl-1-(pp[j].a-pp[j].c))/pp[j].c); } return sum;}void solve(){ ll i,j,le,mid,ri,t; le=mi; ri=ma; while(le<ri) { mid=(le+ri)>>1; t=calnum(le,mid); if(t&1LL) ri=mid; else le=mid+1; } id=le; cnt=calnum(le,le);}int main(){ int i,j,t,test; while(~scanf("%I64d",&n)) { mi=1000000000000LL; ma=0; for(i=1; i<=n; i++) { scanf("%I64d%I64d%I64d",&pp[i].a,&pp[i].b,&pp[i].c); mi=min(pp[i].a,mi); ma=max(ma,pp[i].b); } if(!(calnum(mi,ma)&1)) printf("DC Qiang is unhappy.\n"); else { solve(); printf("%I64d %I64d\n",id,cnt); } } return 0;}