Submission #36002

#TimeUsernameProblemLanguageResultExecution timeMemory
36002Dat160601Fortune Telling 2 (JOI14_fortune_telling2)C++14
0 / 100
96 ms16112 KiB
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back #define fi first #define se second int n,q; int a[200007],b[200007],bit[200007],it[800007],res[200007]; long long ans=0; vector < pair <int,int> > query,qr[200007]; int read(){ int x; scanf("%d",&x); return x; } void upd(int pos){ for(int i=pos;i<=n;i+=i&-i){ bit[i]++; } } long long get(int pos){ long long res=0; for(int i=pos;i>=1;i-=i&-i){ res+=bit[i]; } return res; } void init(int k,int l,int r){ if(l==r){ it[k]=query[l-1].se; return; } int mid=(l+r)/2; init(k*2,l,mid); init(k*2+1,mid+1,r); it[k]=max(it[k*2],it[k*2+1]); } int get(int k,int l,int r,int L,int R){ if(l>R || r<L || l>r) return 0; if(l>=L && r<=R){ return it[k]; } int mid=(l+r)/2; return max(get(k*2,l,mid,L,R),get(k*2+1,mid+1,r,L,R)); } int main(){ n=read(); q=read(); for(int i=1;i<=n;i++){ a[i]=read(); b[i]=read(); } for(int i=1;i<=q;i++){ int val=read(); query.pb(mp(val,i)); } sort(query.begin(),query.end()); init(1,1,q); for(int i=1;i<=n;i++){ int mi=min(a[i],b[i]); int mx=max(a[i],b[i]); int lef=lower_bound(query.begin(),query.end(),mp(mi,0))-query.begin(); int rig=lower_bound(query.begin(),query.end(),mp(mx,0))-query.begin()-1; lef++; rig++; //cout<<lef<<" "<<rig<<" "<<get(1,1,q,lef,rig)<<endl; if(lef<=rig){ qr[rig+1].pb(mp(i,get(1,1,q,lef,rig))); if(a[i]<b[i]) swap(a[i],b[i]); } else{ qr[rig+1].pb(mp(i,1)); } } for(int i=q;i>=1;i--){ upd(query[i-1].se); for(int j=0;j<(int)qr[i].size();j++){ int x=qr[i][j].fi; res[x]=(get(n)-get(qr[i][j].se-1))%2; } } for(int i=1;i<=n;i++){ if(res[i]==0) ans+=a[i]; else ans+=b[i]; } printf("%lld",ans); }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int read()':
fortune_telling2.cpp:13:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&x);
                ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...