Submission #303649

#TimeUsernameProblemLanguageResultExecution timeMemory
303649myungwooComparing Plants (IOI20_plants)C++11
100 / 100
1529 ms17752 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<<20, ST = TS/2-1; int N, K, R[MAXN*2]; int A[MAXN*2], B[MAXN*2]; struct SegTree{ template <typename T> struct Value{ T value, lazysum; }; Value<int> tree[TS]; void build(int arr[]){ memset(tree, 0, sizeof(tree)); for (int i=ST+1;i<TS;i++) tree[i].value = i-ST <= N+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); } } segtree; void get(int perm[]) { segtree.build(R); stack <int> wait; for (int ord=1;ord<=N+N;ord++){ int x = segtree.findzero(1); while (!x){ int q = wait.top(); wait.pop(); segtree.update(1, 1, TS/2, q, N+N, -1); x = segtree.findzero(1); } perm[x] = ord; segtree.update(1, 1, TS/2, x, x, 1e9); segtree.update(1, 1, TS/2, max(1, x-K+1), x-1, -1); if (x-K+1 < 1) wait.push(N+N-(1-(x-K+1))+1); } } void init(int K, vector<int> r) { ::K = K; N = r.size(); for (int i=1;i<=N;i++) R[N+i] = R[i] = r[i-1]; get(A); for (int i=1;i<=N+N;i++) R[i] = K-R[i]-1; get(B); } int compare_plants(int x, int y) { if (x > y) return -compare_plants(y, x); x++; y++; if (A[x] > A[y] || B[y] > B[x+N]) return -1; if (B[x] > B[y] || A[y] > A[x+N]) return 1; return 0; }

Compilation message (stderr)

plants.cpp: In member function 'void SegTree::update(int, int, int, int, int, const int&)':
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...