Submission #835993

#TimeUsernameProblemLanguageResultExecution timeMemory
835993maomao90Comparing Plants (IOI20_plants)C++17
Compilation error
0 ms0 KiB
// I can do all things through Christ who strengthens me // Philippians 4:13 #include "plants.h" #include <bits/stdc++.h> using namespace std; #define REP(i, j, k) for (int i = j; i < (k); i++) #define RREP(i, j, k) for (int i = j; i >= (k); i--) template <class T> inline bool mnto(T &a, const T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T &a, const T b) {return a < b ? a = b, 1 : 0;} typedef long long ll; typedef long double ld; #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; #define ALL(x) x.begin(), x.end() #define SZ(x) (int) x.size() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; typedef tuple<int, int, int> iii; typedef vector<iii> viii; #ifndef DEBUG #define cerr if (0) cerr #endif const int INF = 1000000005; const ll LINF = 1000000000000000005; const int MAXN = 200005; int n, k; vi r; int bad[MAXN]; bool vis[MAXN]; int h[MAXN]; #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1 struct SegTree { pair<ii, int> mx[MAXN * 4]; ii lz[MAXN * 4]; void init(int u = 1, int lo = 0, int hi = n - 1) { lz[u] = {0, 0}; if (lo == hi) { mx[u] = {{r[lo], 0}, lo}; return; } init(lc, lo, mid); init(rc, mid + 1, hi); mx[u] = max(mx[lc], mx[rc]); } void apply(ii x, int u, int lo, int hi) { mx[u].FI += x.FI; mx[u].SE += x.SE; lz[u].FI += x.FI; lz[u].SE += x.SE; } void propo(int u, int lo, int hi) { if (lz[u] == ii(0, 0)) { return; } MLR; apply(lz[u], lc, lo, mid); apply(lz[u], rc, mid + 1, hi); lz[u] = {0, 0}; } void incre(int s, int e, ii x, int u = 1, int lo = 0, int hi = n - 1) { if (e < s) { incre(s, n - 1, x); incre(0, e, x); return; } if (lo >= s && hi <= e) { apply(x, u, lo, hi); return; } MLR; propo(u, lo, hi); if (s <= mid) { incre(s, e, x, lc, lo, mid); } if (e > mid) { incre(s, e, x, rc, mid + 1, hi); } mx[u] = max(mx[lc], mx[rc]); } pair<ii, int> qmx(int s, int e, int u = 1, int lo = 0, int hi = n - 1) { if (e < s) { return max(qmx(s, n - 1), qmx(0, e)); } if (lo >= s && hi <= e) { return mx[u]; } MLR; propo(u, lo, hi); pair<ii, int> res = {{-INF, -INF}, -INF}; if (s <= mid) { mxto(res, qmx(s, e, lc, lo, mid)); } if (e > mid) { mxto(res, qmx(s, e, rc, mid + 1, hi)); } return res; } } st1, st2; void init(int _k, vi _r) { k = _k; r = _r; n = SZ(r); st1.init(); st2.init(); REP (i, 0, n) { if (r[i] == k - 1) { st1.incre(i + 1, i + k - 1, {0, -1}); st2.incre(i, i, {-INF, -INF}); /* REP (j, i + 1, i + k) { bad[j % n]++; } */ } } REP (z, 0, n) { /* int id = -1; REP (i, 0, n) { if (vis[i]) { continue; } if (r[i] == k - 1 && !bad[i]) { id = i; break; } } */ int id = st1.qmx(0, n - 1).SE; h[id] = z; st1.incre(id, id, {-INF, -INF}); st1.incre(id + 1, id + k - 1, {0, 1}); /* vis[id] = 1; REP (j, id + 1, id + k) { bad[j % n]--; } */ st1.incre(id - k + 1, id - 1, {1, 0}); st2.incre(id - k + 1, id - 1, {1, 0}); auto [v, u] = st2.qmx(id - k + 1, id - 1); while (v.FI == k - 1) { st1.incre(u + 1, u + k - 1, {0, -1}); st2.incre(u, u, {-INF, -INF}); tie(v, u) = st2.qmx(id - k + 1, id - 1); } /* RREP (ti, id - 1, id - k + 1) { int i = (ti + n) % n; r[i]++; if (r[i] == k - 1) { REP (j, i + 1, i + k) { bad[j % n]++; } } } */ } return; } int compare_plants(int x, int y) { return h[x] > h[y] ? 1 : -1; }

Compilation message (stderr)

plants.cpp: In member function 'void SegTree::init(int, int, int)':
plants.cpp:55:14: error: 'lc' was not declared in this scope; did you mean 'lz'?
   55 |         init(lc, lo, mid);
      |              ^~
      |              lz
plants.cpp:55:22: error: 'mid' was not declared in this scope
   55 |         init(lc, lo, mid);
      |                      ^~~
plants.cpp:56:14: error: 'rc' was not declared in this scope; did you mean 'r'?
   56 |         init(rc, mid + 1, hi);
      |              ^~
      |              r
plants.cpp: In member function 'void SegTree::apply(ii, int, int, int)':
plants.cpp:60:18: error: no match for 'operator+=' (operand types are 'std::pair<int, int>' and 'int')
   60 |         mx[u].FI += x.FI;
      |                  ^
plants.cpp: In member function 'void SegTree::propo(int, int, int)':
plants.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
plants.cpp:69:9: note: in expansion of macro 'MLR'
   69 |         MLR;
      |         ^~~
plants.cpp: In member function 'void SegTree::incre(int, int, ii, int, int, int)':
plants.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
plants.cpp:84:9: note: in expansion of macro 'MLR'
   84 |         MLR;
      |         ^~~
plants.cpp: In member function 'std::pair<std::pair<int, int>, int> SegTree::qmx(int, int, int, int, int)':
plants.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
      |                       ~~~^~~~
plants.cpp:101:9: note: in expansion of macro 'MLR'
  101 |         MLR;
      |         ^~~