Submission #1209613

#TimeUsernameProblemLanguageResultExecution timeMemory
1209613simona1230식물 비교 (IOI20_plants)C++20
30 / 100
951 ms76828 KiB
#include "plants.h" #include <bits/stdc++.h> #define pb push_back using namespace std; const int logg=20; const int maxn=2*1e5+5; struct node { int vl,id,lz; node() {} node(int _vl,int _id,int _lz) { vl=_vl; id=_id; lz=_lz; } }; node t[4*maxn]; node pull(node lf,node rt) { node h=lf; if(lf.vl>rt.vl)h=rt; return h; } void push(int i,int l,int r) { t[i].vl+=t[i].lz; if(l!=r) { t[i*2].lz+=t[i].lz; t[i*2+1].lz+=t[i].lz; } t[i].lz=0; } void updi(int i,int l,int r,int id,int vl) { push(i,l,r); if(l==r) { t[i].vl=vl; t[i].id=l; return; } int m=(l+r)/2; push(i*2,l,m); push(i*2+1,m+1,r); if(id<=m)updi(i*2,l,m,id,vl); else updi(i*2+1,m+1,r,id,vl); t[i]=pull(t[i*2],t[i*2+1]); } void updr(int i,int l,int r,int ql,int qr) { push(i,l,r); if(ql>qr)return; if(ql<=l&&r<=qr) { t[i].lz-=1; push(i,l,r); return; } int m=(l+r)/2; updr(i*2,l,m,ql,min(qr,m)); updr(i*2+1,m+1,r,max(m+1,ql),qr); t[i]=pull(t[i*2],t[i*2+1]); } node query(int i,int l,int r,int ql,int qr) { push(i,l,r); if(ql>qr)return {maxn,0,0}; if(ql<=l&&r<=qr)return t[i]; int m=(l+r)/2; return pull(query(i*2,l,m,ql,min(qr,m)),query(i*2+1,m+1,r,max(m+1,ql),qr)); } int g[maxn],op[maxn]; int sz,num; int h[4*maxn]; void act(int i,int l,int r,int id,int vl) { if(l==r) { h[i]=vl; return; } int m=(l+r)/2; if(id<=m)act(i*2,l,m,id,vl); else act(i*2+1,m+1,r,id,vl); h[i]=max(h[i*2],h[i*2+1]); } int qry(int i,int l,int r,int id) { if(l>id)return 0; if(r<=id) { //cout<<l<<" "<<r<<" "<<id<<" "<<h[i]<<endl; return h[i]; } int m=(l+r)/2; return max(qry(i*2,l,m,id),qry(i*2+1,m+1,r,id)); } int lf[maxn][logg],rt[maxn][logg]; int sl[maxn][logg],sr[maxn][logg]; int kk; void init(int k, std::vector<int> r) { kk=k; num=r.size(); sz=r.size(); for(int i=0; i<r.size(); i++) updi(1,0,sz-1,i,r[i]); while(1) { stack<int> s; node x=query(1,0,sz-1,0,sz-1); if(x.vl!=0)break; s.push(x.id); while(s.size()) { int y=s.top(); node z=query(1,0,sz-1,max(0,y-k+1),y-1); if(y-k+1<0)z=pull(z,query(1,0,sz-1,sz+(y-k+1),sz-1)); if(z.vl==0)s.push(z.id); else { op[num]=y; g[y]=num--; updr(1,0,sz-1,max(0,y-k+1),y-1); if(y-k+1<0) updr(1,0,sz-1,sz+(y-k+1),sz-1); updi(1,0,sz-1,y,maxn); s.pop(); } } } for(int i=0;i<sz;i++) act(1,1,sz,g[i],0); for(int i=sz-k+1;i<sz;i++) { //cout<<"++ "<<g[i]<<endl; act(1,1,sz,g[i],g[i]); } for(int i=0;i<sz;i++) { int x=i-k; if(x<0)x+=sz; act(1,1,sz,g[x],0); //cout<<"-- "<<g[x]<<endl; if(i) { //cout<<"++ "<<g[i-1]<<endl; act(1,1,sz,g[i-1],g[i-1]); } x=qry(1,1,sz,g[i]); if(x==0)x=-1; else x=op[x]; lf[i][0]=x; sl[i][0]=i-x; if(i<x)sl[i][0]=i+sz-x; //cout<<i<<" "<<x<<endl; } for(int i=0;i<sz;i++) act(1,1,sz,g[i],0); for(int i=1;i<k;i++) { //cout<<"++ "<<g[i]<<endl; act(1,1,sz,g[i],g[i]); } for(int i=0;i<sz;i++) { int x=i+k-1; if(x>=sz)x-=sz; act(1,1,sz,g[x],g[x]); act(1,1,sz,g[i],0); x=qry(1,1,sz,g[i]); if(x==0)x=-1; else x=op[x]; rt[i][0]=x; sr[i][0]=x-i; if(x<i)sr[i][0]=sz-i+x; //cout<<i<<" "<<x<<endl; } for(int j=1;j<logg;j++) for(int i=0;i<sz;i++) { if(lf[i][j-1]==-1)lf[i][j]=-1; else lf[i][j]=lf[lf[i][j-1]][j-1],sl[i][j]=sl[lf[i][j-1]][j-1]+sl[i][j-1]; if(rt[i][j-1]==-1)rt[i][j]=-1; else rt[i][j]=rt[rt[i][j-1]][j-1],sr[i][j]=sr[rt[i][j-1]][j-1]+sr[i][j-1]; //cout<<i<<" "<<j<<" "<<lf[i][j]<<" "<<rt[i][j]<<endl; } /*for(int i=0;i<r.size();i++) cout<<g[i]<<" "; cout<<endl;*/ } int check(int x,int y) { int z=x; int brk=x+sz-y; if(x>y)brk=x-y; //cout<<brk<<endl; for(int i=logg-1;i>=0;i--) { if(lf[z][i]!=-1&&sl[z][i]<=brk) brk-=sl[z][i],z=lf[z][i]; } //cout<<"! "<<z<<endl; if(g[z]>=g[y]&&brk<kk)return 1; z=x; brk=y-x; if(x>y)brk=sz-x+y; //cout<<brk<<endl; for(int i=logg-1;i>=0;i--) { if(rt[z][i]!=-1&&sr[z][i]<=brk) brk-=sr[z][i],z=rt[z][i]; } //cout<<"!! "<<z<<endl; //cout<<"2- "<<z<<endl; if(g[z]>=g[y]&&brk<kk)return 1; return 0; } int compare_plants(int x, int y) { int c1=check(x,y); int c2=check(y,x); //cout<<x<<" ? "<<y<<" "<<c1<<" "<<c2<<endl; if(c1&&!c2)return 1; if(!c1&&c2)return -1; return 0; } /* 300 100 14 96 46 77 29 73 9 54 92 96 85 49 49 69 81 95 10 36 55 54 65 85 27 65 96 90 72 25 5 77 21 27 75 49 55 58 69 28 98 39 47 31 81 94 41 60 97 49 15 41 7 5 32 87 94 69 15 55 79 94 97 62 90 75 38 29 30 9 90 58 26 8 58 7 33 66 34 71 70 50 70 41 91 71 75 42 12 63 31 17 45 37 33 56 32 8 14 4 8 69 31 73 64 8 60 4 11 41 10 20 3 29 79 34 27 80 54 2 17 12 7 8 1 91 23 19 34 61 10 78 81 16 5 62 51 27 22 77 55 79 18 75 13 95 76 0 52 9 86 13 93 75 17 8 97 48 64 9 35 69 93 2 32 6 91 81 60 89 42 81 85 48 51 48 53 54 32 61 44 45 67 3 71 47 94 39 92 44 30 43 34 99 57 83 26 59 76 60 94 92 80 78 48 18 75 78 36 60 6 77 38 49 47 64 60 82 67 27 25 21 79 75 33 97 99 76 17 47 21 17 15 45 74 51 55 7 95 29 88 81 51 33 2 14 36 1 43 41 74 5 85 73 56 30 62 41 56 28 32 29 74 98 17 18 82 60 43 85 81 53 7 83 63 72 44 55 44 99 8 4 85 1 23 48 38 27 34 68 4 68 95 81 9 24 59 59 0 89 27 99 3 156 216 66 213 37 210 106 141 24 210 6 187 48 219 17 142 207 208 71 120 47 113 62 242 58 118 88 223 */
#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...