제출 #397666

#제출 시각아이디문제언어결과실행 시간메모리
397666Antekb식물 비교 (IOI20_plants)C++14
11 / 100
4208 ms2097156 KiB
#include "plants.h" #include<bits/stdc++.h> #define pb(x) push_back(x) #define mp(x, y) make_pair(x, y) #define st first #define nd second using namespace std; const int N=(1<<18); int lazy[2*N]; pair<int, int> maks[2*N]; void prop1(int v){ if(!lazy[v] || v>N)return; int l=2*v, r=l+1; lazy[l]+=lazy[v]; lazy[r]+=lazy[v]; maks[l].st+=lazy[v]; maks[r].st+=lazy[v]; lazy[v]=0; } void add(int v, int l, int r ,int L, int R, int c){ //if(v==1)cout<<"a"<<l<<" "<<r<<" "<<c<<"\n"; //cout<<v<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<"\n"; if(l==L && r==R){ lazy[v]+=c; maks[v].st+=c; return; } prop1(v); int M=(L+R)>>1; if(l<=M)add(2*v, l, min(M, r), L, M, c); if(r>M)add(2*v+1, max(M+1, l), r, M+1, R, c); maks[v]=max(maks[2*v], maks[2*v+1]); return; } pair<int, int> quer1(int v, int l, int r, int L, int R){ if(l==L && r==R){ return maks[v]; } int M=(L+R)>>1; prop1(v); pair<int, int> ans=mp(0, 0); if(l<=M)ans=max(ans, quer1(2*v, l, min(M, r), L, M)); if(r>M)ans=max(ans, quer1(2*v+1, max(M+1, l), r, M+1, R)); return ans; } int lazy2[2*N]; pair<int, int> ma[2*N]; void prop2(int v){ if(!lazy2[v] || v>N)return; int l=2*v, r=l+1; lazy2[l]+=lazy2[v]; lazy2[r]+=lazy2[v]; ma[l].st+=lazy2[v]; ma[r].st+=lazy2[v]; lazy2[v]=0; } void add2(int v, int l, int r ,int L, int R, int c){ //if(v==1)cout<<"b"<<l<<" "<<r<<" "<<c<<"\n"; //cout<<"c"<<"\n"; if(l==L && r==R){ lazy2[v]+=c; ma[v].st+=c; return; } prop2(v); int M=(L+R)>>1; if(l<=M)add2(2*v, l, min(M, r), L, M, c); if(r>M)add2(2*v+1, max(M+1, l), r, M+1, R, c); ma[v]=max(ma[2*v], ma[2*v+1]); return; } pair<int, int> quer2(int v, int l, int r, int L, int R){ if(l==L && r==R){ return ma[v]; } int M=(L+R)>>1; prop2(v); pair<int, int> ans=mp(0, 0); if(l<=M)ans=max(ans, quer2(2*v, l, min(M, r), L, M)); if(r>M)ans=max(ans, quer2(2*v+1, max(M+1, l), r, M+1, R)); return ans; } void check(int k, int n){ while(maks[1].st==k){ //cout<<"b\n"; int v=1; while(v<N){ prop1(v); if(maks[2*v].st==k)v*=2; else v=2*v+1; } add(1, v-N, v-N, 0, N-1, -N); add2(1, v-N, v-N, 0, N-1, N); if(v-N<n-1)add2(1, v-N+1, min(v-N+k, n-1), 0, N-1, -1); if(v-N+k>=n)add2(1, 0, v-N+k-n, 0, N-1, -1); } } vector<int> V, V2; struct node{ node* l=nullptr, *r=nullptr; int sum; void upd(){ sum=0; if(l)sum+=l->sum; if(r)sum+=r->sum; } node(node* _l, node* _r) : l(_l), r(_r) {sum=1;} }; node* left(node* v){if(!v)return nullptr; return v->l;} node* right(node* v){if(!v)return nullptr; return v->r;} node* add(node* v, int L, int R, int id){ if(L==R){ return new node(0, 0); } int M=(L+R)>>1; node* u=new node(left(v), right(v)); if(id<=M)u->l=add(left(v), L, M, id); else u->r=add(right(v), M+1, R, id); u->upd(); return u; } node* merge(node* u, node* v){ if(!u)return v; if(!v)return u; node* w=new node(merge(left(u), left(v)), merge(right(u), right(v))); w->upd(); return w; } bool czy(node* v, int L, int R, int id){ if(!v)return 0; if(L==R)return 1; int M=(L+R)>>1; if(id<=M)return czy(left(v), L, M, id); else return czy(right(v), M+1, R, id); } vector<node* > b; int n; void addbit(int l, int r, node* c){ r++; for(l+=n, r+=n; l<r; l>>=1, r>>=1){ if(l&1)b[l]=merge(b[l], c), l++; if(r&1)r--, b[r]=merge(b[r], c); } } void comp(int x){ if(x==1)return; comp(x/2); b[x]=merge(b[x/2], b[x]); } vector<node*> ans; mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); void init(int k, std::vector<int> r) { /*b.clear(); ans.clear(); V.clear(); for(int i=0; i<2*N; i++)maks[i]=ma[i]=mp(0, 0), lazy[i]=lazy2[i]=0; vector<int> perm(r.size()); iota(perm.begin(), perm.end(), 0); shuffle(perm.begin(), perm.end(), rng); for(int i=0; i<r.size(); i++){ cout<<perm[i]; r[i]=0; for(int j=1; j<k; j++){ r[i]+=(perm[i]>perm[(i+j)%r.size()]); } } cout<<"\n"; for(int i=0; i<r.size(); i++)cout<<r[i]<<" "; cout<<"\n";*/ n=r.size(); k--; V.resize(n); for(int i=0; i<n; i++){ ma[N+i].nd=-i; maks[N+i].st=r[i]; maks[N+i].nd=-i; } for(int i=N-1; i>0; i--){ ma[i]=max(ma[2*i], ma[2*i+1]); maks[i]=max(maks[2*i], maks[2*i+1]); } vector<int> S; b.resize(2*n); ans.resize(n); for(int i=0; i<n; i++){ //cout<<"a\n"; check(k, n); while(ma[1].st==N){ S.push_back(-ma[1].nd); add2(1, -ma[1].nd, -ma[1].nd, 0, N-1, -N); //cout<<"+"; } int j=S[i]; //cout<<j<<"\n"; comp(j+n); V[j]=i; b[j+n]=add(b[j+n], 0, N-1, j); ans[j]=b[j+n]; //assert(ans[j]->sum==i+1); //for(int l=0; l<n; l++)cout<<ans[j][l];cout<<"\n"; pair<int, int> u=mp(0,0); if(j<n-1){ add2(1, j+1, min(j+k, n-1), 0, N-1, 1); addbit(j+1, min(j+k, n-1), ans[j]); //u=max(u, quer2(1, j+1, min(j+k, n-1), 0, N-1)); } if(j+k>=n){ add2(1, 0, j+k-n, 0, N-1, 1); addbit(0, j+k-n, ans[j]); //u=max(u, quer2(1, 0, j+k-n, 0, N-1)); } /*if(u.st==N){ b[-u.nd]|=b[j]; cout<<-u.nd<<"x\n"; }*/ u=mp(0, 0); if(j){ add(1, max(j-k, 0), j-1, 0, N-1, 1); addbit(max(j-k, 0), j-1, ans[j]); //u=max(u, quer1(1, max(j-k, 0), j-1, 0, N-1)); } if(j-k<0){ add(1, n+j-k, n-1, 0, N-1, 1); addbit(n+j-k, n-1, ans[j]); //u=max(u, quer1(1, n+j-k, n-1, 0, N-1)); } /*if(u.st==k){ b[-u.nd]|=b[j]; cout<<-u.nd<<"y\n"; }*/ } return; } int compare_plants(int x, int y){ if(czy(ans[x], 0, N-1, y))return 1; if(czy(ans[y], 0, N-1, x))return -1; 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...