Submission #82800

#TimeUsernameProblemLanguageResultExecution timeMemory
82800Bodo171Fortune Telling 2 (JOI14_fortune_telling2)C++14
100 / 100
1624 ms119800 KiB
#include <iostream> #include <vector> #include <algorithm> #include <fstream> #include <map> using namespace std; const int nmax=200005; vector<int> all,qry[nmax]; map<int,int> norm; int aib[3*nmax],arb[12*nmax]; int a[nmax],b[nmax],val[nmax]; int n,k,st,dr,poz,value,ans,i,lim,ind; void update(int nod,int l,int r) { if(l==r) { arb[nod]=value; return; } int m=(l+r)/2; if(poz<=m) update(2*nod,l,m); else update(2*nod+1,m+1,r); arb[nod]=max(arb[2*nod],arb[2*nod+1]); } void query(int nod,int l,int r) { if(st<=l&&r<=dr) { ans=max(ans,arb[nod]); return; } int m=(l+r)/2; if(st<=m) query(2*nod,l,m); if(m<dr) query(2*nod+1,m+1,r); } inline int lbit(int x) { return ((x^(x-1))&x); } void upd(int poz) { for(int idx=poz;idx<=lim;idx+=lbit(idx)) aib[idx]^=1; } int qr(int poz) { int ret=0; for(int idx=poz;idx>0;idx-=lbit(idx)) ret^=aib[idx]; return ret; } int main() { //freopen("data.in","r",stdin); ios_base::sync_with_stdio(false); cin>>n>>k; for(i=1;i<=n;i++) { cin>>a[i]>>b[i]; all.push_back(a[i]); all.push_back(b[i]); } for(i=1;i<=k;i++) { cin>>val[i]; all.push_back(val[i]); } sort(all.begin(),all.end()); unique(all.begin(),all.end()); for(int i=0;i<all.size();i++) norm[all[i]]=i+1; lim=all.size(); for(i=1;i<=k;i++) { poz=norm[val[i]];value=i; update(1,1,lim); } for(i=1;i<=n;i++) { ans=0; st=norm[min(a[i],b[i])];dr=norm[max(a[i],b[i])]-1; if(st>dr) continue; query(1,1,lim); if(ans!=0&&a[i]<b[i]) swap(a[i],b[i]); qry[ans+1].push_back(i); } for(i=k+1;i>=1;i--) { if(i<=k) upd(norm[val[i]]); for(int j=0;j<qry[i].size();j++) { ind=qry[i][j]; poz=norm[min(a[ind],b[ind])]; if(qr(lim)^qr(poz-1)) swap(a[ind],b[ind]); } } long long sum=0; for(i=1;i<=n;i++) sum+=1LL*a[i]; cout<<sum; return 0; }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:70:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<all.size();i++)
                 ~^~~~~~~~~~~
fortune_telling2.cpp:92:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<qry[i].size();j++)
                     ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...