Submission #398127

#TimeUsernameProblemLanguageResultExecution timeMemory
398127AntekbComparing Plants (IOI20_plants)C++14
25 / 100
1421 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; vector<bitset<N> > b; vector<bool> czy; int n; /*void addbit(int l, int r, bitset<N> c){ r++; for(l+=n, r+=n; l<r; l>>=1, r>>=1){ if(l&1){ if(czy[l])b[l]|=c; l++; } if(r&1){ --r; if(czy[r])b[r]|=c; } } } void comp(int x){ if(x==1)return; comp(x/2); b[x]|=b[x/2]; }*/ //vector<bitset<N>> ans; mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); pair<int, int> H[2*N]; typedef pair<int, int> pii; pii getmin(int l, int r){ r++; pii ans=mp(0, 0); for(l+=N, r+=N; l<r; l>>=1, r>>=1){ if(l&1)ans=max(ans, H[l++]); if(r&1)ans=max(ans, H[--r]); } return ans; } void ust(int i, pii val){ for(i+=N, H[i]=val, i>>=1; i>0; i>>=1){ H[i]=max(H[i+i], H[i+i+1]); } } 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(n); //czy.resize(2*n, 1); //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); //czy[j+n]=0; V[j]=i; //ans[j]=b[j+n]; //assert(ans[j].count()==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[n-u.nd]|=b[j+n]; //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, b[j+n]); //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, b[j+n]); //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"; }*/ } for(int i=0; i<n; i++){ H[N+S[i]]=mp(N-i, S[i]); } for(int i=N-1; i>0; i--){ H[i]=max(H[i+i], H[i+i+1]); } for(int j:S){ //cout<<j<<"\n"; b[j][j]=1; pii u=mp(0, 0); if(j<n-1)u=max(u, getmin(j+1, min(j+k, n-1))); if(j+k>=n)u=max(u, getmin(0, j+k-n)); //cout<<u.st<<" "<<u.nd<<"\n"; if(u.st>0)b[u.nd]|=b[j]; u=mp(0, 0); if(j)u=max(u, getmin(max(j-k, 0), j-1)); if(j-k<0)u=max(u, getmin(n+j-k, n-1)); if(u.st>0)b[u.nd]|=b[j]; ust(j, mp(0, 0)); } return; } int compare_plants(int x, int y){ if(b[x][y])return 1; if(b[y][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...