Submission #303979

#TimeUsernameProblemLanguageResultExecution timeMemory
303979myungwooComparing Plants (IOI20_plants)C++17
44 / 100
1652 ms21448 KiB
#include <bits/stdc++.h> #include "plants.h" using namespace std; #define MAXN 200005 #define debug(...) fprintf(stderr, __VA_ARGS__); fflush(stderr); const int TS = 1<<19, ST = TS/2-1; int N, K, R[MAXN]; int A[MAXN], B[MAXN]; template <typename T> struct SegTree{ struct Value{ T value, lazysum; }; vector<Value> tree; SegTree(int arr[]){ 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 s, int e, int l, int r, const int &v){ if (l > r || e < l || r < s) return; if (l <= s && e <= r){ tree[n].value += v, tree[n].lazysum += v; return; } propagate(n); int m = s+e >> 1; update(n*2, s, m, l, r, v); update(n*2+1, m+1, e, 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; } }; void get(int pos[]) { SegTree<int> segtree(R); ZeroContainer zc; for (int ord=1;ord<=N;ord++){ for (;;){ int p = segtree.findzero(1); if (!p) break; zc.insert(p); segtree.update(1, 1, TS/2, p, p, 1e9); } int x = zc.pop_smallest(); pos[x] = ord; // perm[ord] = x segtree.update(1, 1, TS/2, max(1, x-K+1), x-1, -1); if (x-K+1 < 1) segtree.update(1, 1, TS/2, N-(1-(x-K+1))+1, 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]; get(A); for (int i=1;i<=N;i++) debug("%d ", A[i]); debug("\n"); for (int i=1;i<=N;i++) R[i] = K-R[i]-1; get(B); for (int i=1;i<=N;i++) debug("%d ", B[i]); debug("\n"); } int compare_plants(int x, int y) { x++; y++; if (A[x] < A[y] && B[x] > B[y]) return 1; if (A[y] < A[x] && B[y] > B[x]) return -1; return 0; }

Compilation message (stderr)

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:6:20: warning: macro expands to multiple statements [-Wmultistatement-macros]
    6 | #define debug(...) fprintf(stderr, __VA_ARGS__); fflush(stderr);
      |                    ^~~~~~~
plants.cpp:107:25: note: in expansion of macro 'debug'
  107 |  for (int i=1;i<=N;i++) debug("%d ", A[i]); debug("\n");
      |                         ^~~~~
plants.cpp:107:2: note: some parts of macro expansion are not guarded by this 'for' clause
  107 |  for (int i=1;i<=N;i++) debug("%d ", A[i]); debug("\n");
      |  ^~~
plants.cpp:6:20: warning: macro expands to multiple statements [-Wmultistatement-macros]
    6 | #define debug(...) fprintf(stderr, __VA_ARGS__); fflush(stderr);
      |                    ^~~~~~~
plants.cpp:110:25: note: in expansion of macro 'debug'
  110 |  for (int i=1;i<=N;i++) debug("%d ", B[i]); debug("\n");
      |                         ^~~~~
plants.cpp:110:2: note: some parts of macro expansion are not guarded by this 'for' clause
  110 |  for (int i=1;i<=N;i++) debug("%d ", B[i]); debug("\n");
      |  ^~~
plants.cpp: In instantiation of 'void SegTree<T>::update(int, int, int, int, int, const int&) [with T = int]':
plants.cpp:92:40:   required from here
plants.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int m = s+e >> 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...