Submission #680611

#TimeUsernameProblemLanguageResultExecution timeMemory
680611someoneComparing Plants (IOI20_plants)C++14
30 / 100
4059 ms67916 KiB
#include <bits/stdc++.h> #include "plants.h" #define deb first #define fin second #define mid ((deb + fin) >> 1) using namespace std; const int M = 1 << 19, N = 2 * M, T = 19, INF = 1e9 + 42; int n, k, vals[N], corr[N], gauche[T][M], droite[T][M]; set<int> pos0, posMin; int imin[N], nbInf[N], lazy[N], maxi[N]; void set0(int i, bool is0) { if(is0) { auto it = pos0.lower_bound(i); if((*it) <= i + k) posMin.erase((*it)); it--; if(i > (*it) + k && n <= i && i < 2*n) posMin.insert(i); pos0.insert(i); } else { pos0.erase(i); posMin.erase(i); auto it = pos0.lower_bound(i); int nex = (*it); it--; if(nex > (*it) + k && n <= nex && nex < 2*n) posMin.insert(nex); } } inline void applyOp(int i, int add) { lazy[i] += add; nbInf[i] += add; } pair<int, int> update(int i, int deb, int fin, int l, int r, int add) { if(r <= deb || fin <= l) return {INF, -1}; if(l <= deb && fin <= r) { applyOp(i, add); return {nbInf[i], imin[i]}; } applyOp(i*2, lazy[i]); applyOp(i*2+1, lazy[i]); auto ans = min(update(i*2, deb, mid, l, r, add), update(i*2+1, mid, fin, l, r, add)); lazy[i] = 0; nbInf[i] = min(nbInf[i*2], nbInf[i*2+1]); if(nbInf[i] == nbInf[i*2]) imin[i] = imin[i*2]; else imin[i] = imin[i*2+1]; return ans; } void setMax(int i, int val) { i += M; while(i) { maxi[i] = max(maxi[i], val); i >>= 1; } } int getMax(int i, int deb, int fin, int l, int r) { if(r <= deb || fin <= l) return 0; if(l <= deb && fin <= r) return maxi[i]; return max(getMax(i*2, deb, mid, l, r), getMax(i*2+1, mid, fin, l, r)); } inline int getId(int i) { while(i < 0) i += n; while(i >= n) i -= n; return i; } void init(int K, vector<int> r) { k = K; pos0.insert(INF); pos0.insert(-INF); k--; n = (int)r.size(); for(int i = M; i < N; i++) imin[i] = i - M; for(int i = M-1; i > 0; i--) imin[i] = imin[i*2]; for(int i = 0; i < n; i++) { r[i] = k - r[i]; update(1, 0, M, i, i+1, r[i]); if(r[i] == 0) { set0(i, 1); set0(i + n, 1); } } for(int i = 0; i < n; i++) { int id = getId((*posMin.begin())); update(1, 0, M, id, id+1, INF); set0(id, 0); set0(id + n, 0); vals[id] = i+1; corr[i+1] = id; corr[0] = id; setMax(id, i+1); setMax(id + n, i+1); gauche[0][id] = getId(corr[getMax(1, 0, M, id + n - k, id + n)] - id), droite[0][id] = getId(corr[getMax(1, 0, M, id + 1, id + k + 1)] - id); if(gauche[0][id] > 0) gauche[0][id] -= n; if(id >= k) { update(1, 0, M, id - k, id, -1); } else { update(1, 0, M, 0, id, -1); update(1, 0, M, n + id - k, n, -1); } auto pii = update(1, 0, M, 0, n, 0); while(pii.first == 0) { update(1, 0, M, pii.second, pii.second+1, INF); set0(pii.second, 1); set0(pii.second + n, 1); pii = update(1, 0, M, 0, n, 0); } } for(int i = 1; i < T; i++) { for(int j = 0; j < n; j++) { gauche[i][j] = gauche[i-1][getId(j + gauche[i-1][j])] + gauche[i-1][j]; droite[i][j] = droite[i-1][getId(j + droite[i-1][j])] + droite[i-1][j]; } } } int compare_plants(int x, int y) { int ans = 1; if(vals[x] < vals[y]) { swap(x, y); ans = -1; } int idl = x, idr = x, nbl = 0, nbr = 0; for(int i = T-1; i > -1; i--) { int l = getId(gauche[i][idl] + idl), r = getId(droite[i][idr] + idr); if(vals[l] >= vals[y]) { nbl += gauche[i][idl]; idl = l; } if(vals[r] >= vals[y]) { nbr += droite[i][idr]; idr = r; } } int l = x + nbl, r = x + nbr; if((l <= y - n && y - n <= r) || (l <= y && y <= r) || (l <= y + n && y + n <= r)) return ans; 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...