제출 #302413

#제출 시각아이디문제언어결과실행 시간메모리
302413ludo식물 비교 (IOI20_plants)C++14
0 / 100
10 ms8832 KiB
#include<bits/stdc++.h> #include "plants.h" using namespace std; const int LEN = 256 * 1024; // segment tree: int lo[2 * LEN]; // lowest value in range [ L(node), R(node) ) of the **non-negative** numbers. int lazy[2 * LEN]; // decrement to propagate downwards. vector<int> order; int D(int a, int b, int n) { if (a < b) return b - a; else return (n+b) - a; } void propagate(int i) { int x = lazy[i]; lo[i] -= x; lazy[i] = 0; if (i < LEN && x != 0) { lazy[2*i ] += x; lazy[2*i+1] += x; } } void find_zeros(int i, vector<int> &zeros) { propagate(i); assert(lo[i] == 0); if (i >= LEN) { zeros.push_back(i - LEN); } else { if (lo[2*i] == lazy[2*i]) find_zeros(2*i, zeros); if (lo[2*i+1] == lazy[2*i+1]) find_zeros(2*i+1, zeros); } } // node i has range [L, R). Decrement [a, b) by one. void dec(int i, int L, int R, int a, int b, vector<int> &zeros) { if (b <= L || a >= R) return; // outside interval. if (a <= L && R <= b) { // [L, R) \subseteq [a, b). if (++lazy[i] < lo[i]) return; // we have some zero inside this interval. find_zeros(i, zeros); } else { propagate(i); int M = (L+R) / 2; dec(2*i , L, M, a, b, zeros); dec(2*i+1, M, R, a, b, zeros); } } void decrementInterval(int a, int b, vector<int> &zeros) { dec(1, 0, LEN, a, b, zeros); } void set_inf(int i) { vector<int> indices = { i + LEN }; while (indices.back() > 1) { indices.push_back(indices.back() / 2); } while (!indices.empty()) { propagate(indices.back()); indices.pop_back(); } int node = i + LEN; assert(lazy[node] == 0); lo[node] = LEN; while (node > 1) { node /= 2; lo[node] = min( lo[node*2 ] - lazy[node*2 ], lo[node*2+1] - lazy[node*2+1] ); } } void init(int k, vector<int> r) { int n = r.size(); order.assign(n, -1); for (int i=0; i < 2*LEN; i++) lazy[i] = 0; for (int i=0; i < LEN; i++) lo[LEN+i] = i < n ? r[i] : LEN; for (int i = LEN; --i > 0; ) lo[i] = min(lo[2*i], lo[2*i+1]); set<int> candidates, bigGap; // a candidate occurs in bigGap, if the gap to the previous one is >= k. for (int i=0; i<n; i++) { if (r[i] == 0) candidates.insert(i); } assert(!candidates.empty()); int lc = *candidates.rbegin(); for (int c : candidates) { if (D(lc, c, n) >= k) bigGap.insert(c); lc = c; } int ndone = 0, step = -1; while (ndone != n) { step++; assert(!bigGap.empty()); ndone += bigGap.size(); vector<int> v(bigGap.begin(), bigGap.end()); bigGap.clear(); vector<int> newCandidates; for (int i : v) { order[i] = step; set_inf(i); } for (int i : v) { int prev = i - k + 1; if (prev >= 0) { decrementInterval(prev, i, newCandidates); } else { decrementInterval(0, i, newCandidates); decrementInterval(prev + n, n, newCandidates); } } for (int i : newCandidates) { auto it = candidates.lower_bound(i); if (!candidates.empty()) { if (it == candidates.end()) it = candidates.begin(); int inxt = *it; if (D(i, inxt, n) < k) bigGap.erase(inxt); } it = candidates.insert(i).first; if (it == candidates.begin()) { it = candidates.end(); } else { --it; } int iprv = *it; if (D(iprv, i, n) >= k) bigGap.insert(i); } for (int i : v) { candidates.erase(i); // check the gap of the next element. if (candidates.empty()) continue; auto it = candidates.lower_bound(i); if (it == candidates.end()) it = candidates.begin(); int inxt = *it, iprv; if (it == candidates.begin()) iprv = *candidates.rbegin(); else iprv = *(--it); if (D(iprv, inxt, n) >= k) bigGap.insert(inxt); } } return; } int compare_plants(int x, int y) { // order[x] > order[y]: h[x] < h[y] -> -1 // order[x] == order[y]: h[x] == h[y] -> 0 // order[x] < order[y]: h[x] > h[y] -> +1 if (order[x] < order[y]) return +1; if (order[x] > order[y]) 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...