Submission #304386

#TimeUsernameProblemLanguageResultExecution timeMemory
304386myungwooComparing Plants (IOI20_plants)C++17
100 / 100
1363 ms43500 KiB
#include <bits/stdc++.h> #include "plants.h" using namespace std; #define MAXN 200005 #define debug(...) fprintf(stderr, __VA_ARGS__); fflush(stderr); typedef pair<int, int> pii; int N, K, R[MAXN]; int H[MAXN], nxt_r[MAXN][18], nxt_l[MAXN][18]; template <typename T> struct SegTree{ int n_bits, TS, ST; int range_l(int x){ return ((x<<(__builtin_clz(x)-31+n_bits)) ^ (1<<n_bits)) + 1; } int range_r(int x){ return ((x<<(__builtin_clz(x)-31+n_bits) ^ ((1<<(__builtin_clz(x)-31+n_bits))-1)) ^ (1<<n_bits)) + 1; } struct Value{ T value, lazysum; }; vector<Value> tree; SegTree(int arr[]){ n_bits = 32-__builtin_clz(N-1); TS = 1 << n_bits+1; ST = TS/2-1; tree.resize(TS, {0, 0}); for (int i=ST+1;i<TS;i++) tree[i].value = i-ST <= N ? arr[i-ST] : 1e9; for (int i=ST;i;i--) tree[i].value = min(tree[i*2].value, tree[i*2+1].value); } void propagate(int n){ if (n <= ST){ tree[n*2].value += tree[n].lazysum, tree[n*2+1].value += tree[n].lazysum; tree[n*2].lazysum += tree[n].lazysum, tree[n*2+1].lazysum += tree[n].lazysum; } tree[n].lazysum = 0; } void update(int n, int l, int r, const int &v){ int s = range_l(n), e = range_r(n); if (l > r || e < l || r < s) return; if (l <= s && e <= r){ tree[n].value += v, tree[n].lazysum += v; return; } propagate(n); update(n*2, l, r, v); update(n*2+1, l, r, v); tree[n].value = min(tree[n*2].value, tree[n*2+1].value); } int findzero(int n){ if (tree[n].value != 0) return 0; propagate(n); if (n > ST) return n-ST; if (!tree[n*2].value) return findzero(n*2); else if (!tree[n*2+1].value) return findzero(n*2+1); else assert(0); } }; struct ZeroContainer{ set<int> pos, non_covered; set<int>::iterator _left(set<int>::iterator it){ auto ret = it; if (ret == pos.begin()) ret = pos.end(); return --ret; } set<int>::iterator _right(set<int>::iterator it){ auto ret = it; ret++; if (ret == pos.end()) return pos.begin(); return ret; } void insert(int p){ auto it = pos.insert(p).first; auto l = _left(it), r = _right(it); if (l == it || (*it-*l+N)%N >= K) non_covered.insert(p); if (r != it && (*r-*it+N)%N < K) non_covered.erase(*r); } void remove(int p){ auto it = pos.find(p); auto l = _left(it), r = _right(it); if (l != it && r != it && (l == r || (*r-*l+N)%N >= K)) non_covered.insert(*r); pos.erase(it); } int pop_smallest(){ int ret = *non_covered.begin(); non_covered.erase(ret); remove(ret); return ret; } }; int go_left(int n, int d) { return (n - d%N - 1 + N)%N + 1; } int go_right(int n, int d) { return (n + d%N - 1 + N)%N + 1; } void init(int K, vector<int> r) { ::K = K; N = r.size(); for (int i=1;i<=N;i++) R[i] = r[i-1]; { SegTree<int> segtree(R); ZeroContainer zc; for (int ord=N;ord;ord--){ for (;;){ int p = segtree.findzero(1); if (!p) break; zc.insert(p); segtree.update(1, p, p, 1e9); } int x = zc.pop_smallest(); H[x] = ord; segtree.update(1, max(1, x-K+1), x-1, -1); if (x-K+1 < 1) segtree.update(1, N-(1-(x-K+1))+1, N, -1); } } { set <pii> s; for (int i=1;i<=K;i++) s.insert({H[i], i}); for (int i=1;i<=N;i++){ auto it = s.lower_bound({H[i], 0}); if (it != s.begin()){ it--; nxt_r[i][0] = (it->second - i + N) % N; } int t = (i+K-1)%N+1; s.insert({H[t], t}); s.erase({H[i], i}); } } { set <pii> s; for (int i=1;i<K;i++) s.insert({H[i], i}); for (int i=1;i<=N;i++){ int t = (i+K-2)%N+1; auto it = s.lower_bound({H[t], 0}); if (it != s.begin()){ it--; nxt_l[t][0] = (t - it->second + N) % N; } s.insert({H[t], t}); s.erase({H[i], i}); } } for (int i=0;i+1<18;i++) for (int j=1;j<=N;j++){ nxt_l[j][i+1] = min(N+10, nxt_l[go_left(j, nxt_l[j][i])][i] + nxt_l[j][i]); nxt_r[j][i+1] = min(N+10, nxt_r[go_right(j, nxt_r[j][i])][i] + nxt_r[j][i]); } } bool has_left_path(int a, int b) { int d = (a-b+N)%N; for (int i=18;i--;) if (d >= nxt_l[a][i]){ d -= nxt_l[a][i]; a = go_left(a, nxt_l[a][i]); } return (a-b+N)%N < K && H[a] >= H[b]; } bool has_right_path(int a, int b) { int d = (b-a+N)%N; for (int i=18;i--;) if (d >= nxt_r[a][i]){ d -= nxt_r[a][i]; a = go_right(a, nxt_r[a][i]); } return (b-a+N)%N < K && H[a] >= H[b]; } int compare_plants(int a, int b) { a++; b++; if (has_left_path(a, b) || has_right_path(a, b)) return 1; if (has_left_path(b, a) || has_right_path(b, a)) return -1; return 0; }

Compilation message (stderr)

plants.cpp: In instantiation of 'SegTree<T>::SegTree(int*) [with T = int]':
plants.cpp:101:25:   required from here
plants.cpp:23:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   23 |   TS = 1 << n_bits+1; ST = TS/2-1;
      |             ~~~~~~^~
#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...