제출 #528059

#제출 시각아이디문제언어결과실행 시간메모리
528059HappyPacMan식물 비교 (IOI20_plants)C++14
0 / 100
35 ms6368 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 8; const int mlog = 20; const int inf = 1e9; int N,K,seg[4*maxn],lazy[4*maxn],indexing=0,arr[maxn],rev[maxn],lf[mlog][maxn],rg[mlog][maxn]; void push(int id){ lazy[id<<1] += lazy[id]; lazy[id<<1|1] += lazy[id]; seg[id<<1] += lazy[id]; seg[id<<1|1] += lazy[id]; lazy[id] = 0; } void upd(int id,int tl,int tr,int ul,int ur,int v){ if(tl > tr || ul > tr || ur < tl) return; if(ul <= tl && tr <= ur){ seg[id] += v; lazy[id] += v; return; } int tm = (tl+tr)/2; push(id); upd(id<<1,tl,tm,ul,ur,v); upd(id<<1|1,tm+1,tr,ul,ur,v); seg[id] = min(seg[id<<1],seg[id<<1|1]); } int qryfull(int id,int tl,int tr){ if(seg[id] != 0) return -1; if(tl == tr) return tl; int tm = (tl+tr)/2; push(id); int res = -1; if(seg[id<<1] != 0) res = qryfull(id<<1|1,tm+1,tr); else res = qryfull(id<<1,tl,tm); seg[id] = min(seg[id<<1],seg[id<<1|1]); return res; } int qrypart(int id,int tl,int tr,int ql){ if(tl == tr) return seg[id]; int tm = (tl+tr)/2; push(id); int res = -1; if(tm < ql) res = qrypart(id<<1|1,tm+1,tr,ql); else res = qrypart(id<<1,tl,tm,ql); seg[id] = min(seg[id<<1],seg[id<<1|1]); return res; } void rec(int x){ for(int i=1-K;i<0;i++) if(qrypart(1,0,N-1,(x+N+i)%N) == 0) rec((x+N+i)%N); upd(1,0,N-1,x,x,inf); if(x > 0) upd(1,0,N-1,max(0,x-K+1),x,-1); if(0 > x-K+1) upd(1,0,N-1,N+x-K+1,N-1,-1); rev[indexing] = x; arr[x] = indexing++; } void init(int k, std::vector<int> r){ K = k; N = r.size(); for(int i=0;i<N;i++) upd(1,0,N-1,i,i,r[i]); while(qryfull(1,0,N-1) != -1) rec(qryfull(1,0,N-1)); set<int> st; for(int i=1-K;i<0;i++) st.insert(arr[N+i]); for(int i=0;i<N;i++){ auto it = st.lower_bound(arr[i]); if(it == st.begin()) lf[0][i] = -1; else lf[0][i] = rev[*prev(it)]; st.insert(arr[i]); st.erase(arr[(N+i-K+1)%N]); } st.clear(); for(int i=1;i<K;i++) st.insert(arr[i]); for(int i=0;i<N;i++){ auto it = st.lower_bound(arr[i]); if(it == st.begin()) rg[0][i] = -1; else rg[0][i] = rev[*prev(it)]; st.insert(arr[(i+K)%N]); st.erase(arr[(i+1)%N]); } st.clear(); for(int i=1;i<mlog;i++){ for(int j=0;j<N;j++){ if(lf[i-1][j] == -1) lf[i][j] = -1; else lf[i][j] = lf[i-1][lf[i-1][j]]; if(rg[i-1][j] == -1) rg[i][j] = -1; else rg[i][j] = rg[i-1][rg[i-1][j]]; } } } bool comp(int x,int y){ int tx = x; for(int i=mlog-1;i>=0;i--){ if(lf[i][tx] == -1) continue; if(lf[i][tx] > tx){ if(tx < y && y < lf[i][tx]){ tx = lf[i][tx]; } }else{ if(y < lf[i][tx] || tx < y){ tx = lf[i][tx]; } } } int ty = x; for(int i=mlog-1;i>=0;i--){ if(rg[i][ty] == -1) continue; if(rg[i][ty] < ty){ if(rg[i][ty] < y && y < ty){ ty = rg[i][ty]; } }else{ if(y < ty || rg[i][ty] < y){ ty = rg[i][ty]; } } } if(lf[0][tx] != -1 && arr[y] <= arr[tx]) return true; if(rg[0][ty] != -1 && arr[y] <= arr[ty]) return true; if(lf[0][tx] == -1 && y == tx) return true; if(rg[0][ty] == -1 && y == ty) return true; return false; } int compare_plants(int x, int y){ bool a = comp(x,y); if(a) return -1; bool b = comp(y,x); if(b) return 1; assert(false); 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...