Submission #1079595

#TimeUsernameProblemLanguageResultExecution timeMemory
1079595bleahbleahComparing Plants (IOI20_plants)C++17
30 / 100
1341 ms79596 KiB
#include "plants.h" #include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; #define sz(x) ((int)(x).size()) int K, N; const int nmax = 2e5 + 5; template<typename T> struct AINT { vector<T> aint; int n; void init(int n_) { n = n_; aint.assign(2 * n + 5, T()); } template<int dir = 0, class CB> void walk(CB&& cb) { walk<dir>(cb, 0, n - 1); } template<int dir = 0, class CB> void walk(CB&& cb, int l, int r) { walk<dir>(cb, l, r, 1, 0, n - 1); } template<int dir = 0, class CB> void walk(CB&& cb, int l, int r, int node, int cl, int cr) { if(cr < l || r < cl) return; if(l <= cl && cr <= r && !cb(aint[node], cl, cr)) return; int mid = (cl + cr) >> 1, L = node + 1, R = node + (mid - cl + 1) * 2; aint[node].push(aint[L], aint[R]); if(dir == 0) { walk<dir>(cb, l, r, L, cl, mid); walk<dir>(cb, l, r, R, mid + 1, cr); } if(dir == 1) { walk<dir>(cb, l, r, R, mid + 1, cr); walk<dir>(cb, l, r, L, cl, mid); } aint[node].pull(aint[L], aint[R]); } }; struct MinFindUnit { int mn; int lazy = 0; void push(MinFindUnit& L, MinFindUnit& R) { if(lazy == 0) return; L.lazy += lazy; R.lazy += lazy; R.mn += lazy; L.mn += lazy; lazy = 0; return; } void pull(MinFindUnit& L, MinFindUnit& R) { mn = min(L.mn, R.mn); return; } }; struct MinFind : AINT<MinFindUnit> { int query_next(int t, int limit) { if(aint[1].mn > limit) return -1; for(int itt = 0; itt < 2; itt++) { walk([&](auto& a, int cl, int cr) { if(t < cl) return 0; if(cr < t) return 0; if(a.mn > limit) { t = cr + 1; return 0; } if(cl == cr) { return 0; } return 1; }, t, n - 1); if(t == n) t = 0; } return t; } int query_prev(int t, int limit) { if(aint[1].mn > limit) return -1; for(int itt = 0; itt < 2; itt++) { walk<1>([&](auto& a, int cl, int cr) { if(t < cl) return 0; if(cr < t) return 0; if(a.mn > limit) { t = cl - 1; return 0; } if(cl == cr) { return 0; } return 1; }, 0, t); if(t == -1) t = n - 1; } return t; } void add(int l, int r, int x) { if(l > r) { add(l, N - 1, x), add(0, r, x); return; } walk([&](auto& a, int cl, int cr) { a.mn += x; a.lazy += x; return 0; }, l, r); } void set(int p, int x) { set(p, p, x); } void set(int l, int r, int x) { walk([&](auto& a, int cl, int cr) { if(cl != cr) return 1; a.mn = x; a.lazy = 0; return 0; }, l, r); } int query(int l, int r, int x = 1e9 + 6) { if(l > r) return min(query(l, N - 1), query(0, r)); walk([&](auto& a, int cl, int cr) { x = min(x, a.mn); return 0; }, l, r); return x; } }; MinFind nextinqueue; namespace Queue { int next[nmax]; MinFind inside; auto rdist = [](int x, int d) { return d < x? N - x + d : d - x; }; auto ldist = [](int x, int d) { return d <= x? x - d : x + N - d; }; set<int> heads; void init() { inside.init(N); inside.set(0, N - 1, 1); } void insert(int node) { nextinqueue.set(node, 1e9 + 5); heads.emplace(node); inside.set(node, 0); next[node] = -1; int nx = inside.query_next((node + 1) % N, 0); int pr = inside.query_prev((node - 1 + N) % N, 0); if(nx != node && rdist(node, nx) < K) { next[node] = nx; if(heads.count(nx)) heads.erase(nx); } if(pr != node && ldist(node, pr) < K) { heads.erase(node); next[pr] = node; } } vector<int> prune() { vector<int> rez; for(auto x : heads) rez.emplace_back(x), inside.set(x, 1); heads.clear(); for(auto x : rez) if(next[x] != -1) heads.emplace(next[x]); return rez; } } vector<int> topsort; #define left ofia #define right goa int left[nmax][18], jumpl[nmax][18]; int right[nmax][18], jumpr[nmax][18]; void init(int k__, std::vector<int> r) { auto T = r; K = k__; N = sz(r); topsort.resize(N); Queue::init(); nextinqueue.init(N); vector<int> erased(N, 0); nextinqueue.walk([&](auto& a, int cl, int cr) { if(cl != cr) return 1; a.mn = r[cl]; return 0; }); for(int i = 0; i < sz(r); i++) if(r[i] == 0) erased[i] = 1, Queue::insert(i); int color = 0; while(sz(Queue::heads)) { auto rem = Queue::prune(); ++color; for(auto x : rem) topsort[x] = color; for(auto x : rem) nextinqueue.add((x - K + 1 + N) % N, x, -1); while(1) { int x = nextinqueue.query_next(0, 0); if(x == -1) break; Queue::insert(x); } } vector<int> idx(N); iota(all(idx), 0); sort(all(idx), [&](int a, int b) { return topsort[a] > topsort[b]; }); MinFind inserted; inserted.init(N); inserted.set(0, N - 1, 1e9 + 5); auto cmp = [&](int a, int b) { return make_pair(topsort[a], a) < make_pair(topsort[b], b); }; set<int, decltype(cmp)> heap(cmp); for(int i = 0; i < K; i++) heap.insert(i); for(int i = 0, r = K; i < N; i++, r = (r + 1) % N) { auto it = heap.upper_bound(i); if(it == heap.end()) right[i][0] = i; else right[i][0] = *it; heap.erase(i); heap.insert(r); } heap.clear(); for(int i = 0; i < K - 1; i++) heap.insert(i); for(int l = 0, i = K - 1; l < N; i = (i + 1) % N, l++) { heap.insert(i); auto it = heap.upper_bound(i); if(it == heap.end()) left[i][0] = i; else left[i][0] = *it; heap.erase(l); } for(int i = 0; i < N; i++) { jumpr[i][0] = Queue::rdist(i, right[i][0]); jumpl[i][0] = Queue::ldist(i, left[i][0]); } for(int step = 1; step < 18; step++) for(int i = 0; i < N; i++) left[i][step] = left[left[i][step - 1]][step - 1], jumpl[i][step] = jumpl[i][step - 1] + jumpl[left[i][step - 1]][step - 1], right[i][step] = right[right[i][step - 1]][step - 1], jumpr[i][step] = jumpr[i][step - 1] + jumpr[right[i][step - 1]][step - 1]; return; } bool compare_smaller(int x, int y) { auto rdist = [&](int d) { return d < x? N - x + d : d - x; }; auto ldist = [&](int d) { return d <= x? x - d : x + N - d; }; int st = x, buffer = rdist(y); for(int i = 17; i >= 0; i--) { if(buffer < jumpr[st][i]) continue; buffer -= jumpr[st][i]; st = right[st][i]; } if(st == y) return 1; if(rdist(y) - rdist(st) < K && topsort[y] > topsort[st]) return 1; st = x; buffer = ldist(y); for(int i = 17; i >= 0; i--) { if(buffer < jumpl[st][i]) continue; buffer -= jumpl[st][i]; st = left[st][i]; } if(st == y) return 1; if(ldist(y) - ldist(st) < K && topsort[y] > topsort[st]) return 1; return 0; } int compare_plants(int x, int y) { return compare_smaller(x, y)? 1 : compare_smaller(y, x)? -1 : 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...