Submission #420921

#TimeUsernameProblemLanguageResultExecution timeMemory
420921mosiashvililukaComparing Plants (IOI20_plants)C++14
11 / 100
4077 ms6948 KiB
#include "plants.h" #include<bits/stdc++.h> using namespace std; int a,b,c,d,e,i,j,ii,jj,zx,xc,k,R[200009],cnt,f[200009],seg[800009],seg2[800009],segmn[800009],za,l,r,z,zz,x,y,RE[200009]; bool bo[309][309]; set <int> s; set <int>::iterator it,tt; set <pair <int, int> > st; set <pair <int, int> >::iterator IT; void pushdown(int q, int w, int rr){ if(q!=w){ seg2[rr*2]+=seg2[rr]; seg2[rr*2+1]+=seg2[rr]; } segmn[rr]+=seg2[rr]; seg2[rr]=0; } void upd(int q, int w, int rr){ pushdown(q,w,rr); if(q>r||w<l) return; if(q>=l&&w<=r){ seg2[rr]+=z; pushdown(q,w,rr); return; } upd(q,(q+w)/2,rr*2); upd((q+w)/2+1,w,rr*2+1); if(segmn[rr*2]<segmn[rr*2+1]){ seg[rr]=seg[rr*2];segmn[rr]=segmn[rr*2]; } if(segmn[rr*2]>segmn[rr*2+1]){ seg[rr]=seg[rr*2+1];segmn[rr]=segmn[rr*2+1]; } if(segmn[rr*2]==segmn[rr*2+1]){ segmn[rr]=segmn[rr*2+1]; seg[rr]=min(seg[rr*2],seg[rr*2+1]); } } void UPD(int q, int w, int rr){ l=q+1;r=w+1;z=rr; upd(1,za,1); } void read(int q, int w, int rr){ pushdown(q,w,rr); if(q>r||w<l) return; if(q>=l&&w<=r){ if(z>segmn[rr]){ z=segmn[rr];zz=seg[rr]; }else{ if(z==segmn[rr]){ if(zz>seg[rr]) zz=seg[rr]; } } return; } read(q,(q+w)/2,rr*2); read((q+w)/2+1,w,rr*2+1); } void READ(int q, int w){ q++;w++; while(q<=w){ l=q;r=w;z=a+3;zz=a+3; read(1,za,1); if(z!=0||zz>w) break; zz--; it=s.lower_bound(zz); if(it==s.end()) it=s.begin(); if(it!=s.begin()){ tt=it;tt--; }else{ tt=s.end();tt--; } st.erase(st.lower_bound(make_pair(((*it)+a-(*tt))%a,(*it)))); st.insert(make_pair(((*it)+a-zz)%a,(*it))); st.insert(make_pair((zz+a-(*tt))%a,zz)); s.insert(zz); zz++; q=zz+1; } } void init(int Kk, vector<int> Rr) { a=Rr.size();k=Kk-1; for(i=0; i<a; i++){ R[i]=Rr[i]; } za=1; while(za<a) za*=2; for(x=0; x<a; x++){ s.clear();st.clear(); for(i=0; i<=za*2; i++){ seg2[i]=0; } for(i=0; i<a; i++){ seg[za+i]=i+1;segmn[za+i]=R[i]; if(R[i]==0){ s.insert(i); } } for(i=za-1; i>=1; i--){ if(segmn[i*2]<segmn[i*2+1]){ seg[i]=seg[i*2];segmn[i]=segmn[i*2]; } if(segmn[i*2]>segmn[i*2+1]){ seg[i]=seg[i*2+1];segmn[i]=segmn[i*2+1]; } if(segmn[i*2]==segmn[i*2+1]){ segmn[i]=segmn[i*2+1]; seg[i]=min(seg[i*2],seg[i*2+1]); } } for(it=s.begin(); it!=s.end(); it++){ tt=it;tt++; /*if(tt==s.end()){ tt=s.begin(); st.insert(make_pair((*tt)+a-(*it),(*tt))); }else{ st.insert(make_pair((*tt)-(*it),(*tt))); }*/ if(tt==s.end()) tt=s.begin(); st.insert(make_pair(((*tt)+a-(*it))%a,(*tt))); } cnt=a; /*cout<<cnt<<" JJF"; exit(0);*/ //cout<<s.size()<<" "<<st.size()<<endl; while(cnt>0){ IT=st.end();IT--; i=(*IT).second; if(i==x){ if(IT!=st.begin()){ IT--; if((*IT).first==0||(*IT).first>k){ i=(*IT).second; }else{ } } } if(i==x) break; bo[x][i]=1; f[i]=cnt;cnt--; if(cnt==0) break; if(i-k>=0){ UPD(i-k,i-1,-1); READ(i-k,i-1); }else{ UPD(0,i-1,-1); UPD(a-(k-i),a-1,-1); READ(0,i-1); READ(a-(k-i),a-1); } /*cout<<i<<" kala1"<<endl; cout<<s.size()<<" "<<st.size()<<endl; exit(0);*/ s.erase(s.lower_bound(i)); it=s.lower_bound(i); if(it==s.end()) it=s.begin(); if(it!=s.begin()){ tt=it;tt--; }else{ tt=s.end();tt--; } st.erase(st.lower_bound(make_pair(((*it)+a-i)%a,(*it)))); st.erase(st.lower_bound(make_pair((i+a-(*tt))%a,i))); st.insert(make_pair(((*it)+a-(*tt))%a,(*it))); /*cout<<i<<" kala2"; exit(0);*/ l=i+1;r=i+1;z=a+3; upd(1,za,1); /*cout<<i<<" kala3"; exit(0);*/ } } return; } int compare_plants(int Xx, int Yy) { x=Xx;y=Yy; /*if(f[x]>f[y]){ return 1; }else{ return -1; }*/ if(bo[x][y]==1&&bo[y][x]==1) return 0; if(bo[x][y]==0) return 1; return -1; } /*int main(){ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); int TES=0,TE=0; cin>>a>>k>>TES; vector <int> Rr; Rr.resize(a); for(i=0; i<a; i++){ cin>>R[i]; RE[i]=R[i]; //Rr.push_back(c); } for(i=0; i<a; i++){ for(j=i+1; j<i+k; j++){ if(R[j%a]>R[i]) Rr[i]++; } } init(k,Rr); for(i=0; i<a; i++){ cout<<f[i]<<" "; } cout<<endl; //return 0; for(TE=1; TE<=TES; TE++){ cin>>c>>d; cout<<compare_plants(c,d)<<endl; } for(int I=0; I<a; I++){ for(int J=0; J<a; J++){ if(I==J) continue; e=compare_plants(I,J); if(e==0){ cout<<"WRONG ANSWER: "<<I<<" "<<J; return 0; } if(RE[I]>RE[J]){ if(e==-1){ cout<<"WRONG ANSWER: "<<I<<" "<<J; return 0; } }else{ if(e==1){ cout<<"WRONG ANSWER: "<<I<<" "<<J; return 0; } } } } cout<<"ACCEPTED"; return 0; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...