Submission #629840

#TimeUsernameProblemLanguageResultExecution timeMemory
629840MilosMilutinovicComparing Plants (IOI20_plants)C++14
100 / 100
1256 ms133644 KiB
#include "plants.h" #include <bits/stdc++.h> #define rep(i, n) for(int i = 0; i < (int)(n); i ++) #define rep1(i, n) for(int i = 1; i <= (int)(n); i ++) #define MP make_pair using namespace std; typedef long long LL; typedef pair<int, int> PII; const int INF = 1e9; int n, k, h[400005]; int jumpL[400005][25]; int jumpR[400005][25]; struct segt { PII dat[4000005]; int tag[4000005]; segt() { rep(i, 4000005) dat[i] = MP(1e9, 1e9); } void pull(int cv) { dat[cv] = min(dat[cv << 1], dat[cv << 1 | 1]); } void upd(int cv, int v) { dat[cv].first -= v; tag[cv] += v; pushtag(cv); } void pushtag(int cv) { if(tag[cv] == 0) return; dat[cv << 1 | 0].first -= tag[cv]; dat[cv << 1 | 1].first -= tag[cv]; tag[cv << 1 | 0] += tag[cv]; tag[cv << 1 | 1] += tag[cv]; tag[cv] = 0; } void build(int cv = 1, int cl = 0, int cr = n - 1) { if(cl == cr) { dat[cv] = MP(h[cl], cl); return; } int mid = cl + cr >> 1; build(cv << 1 | 0, cl, mid); build(cv << 1 | 1, mid + 1, cr); pull(cv); } void modify(int ql, int qr, int v, int cv = 1, int cl = 0, int cr = n - 1) { if(cr < ql || cl > qr || cl > cr) return; if(ql <= cl && cr <= qr) { upd(cv, v); return; } int mid = cl + cr >> 1; pushtag(cv); modify(ql, qr, v, cv << 1 | 0, cl, mid); modify(ql, qr, v, cv << 1 | 1, mid + 1, cr); pull(cv); } PII query(int ql, int qr, int cv = 1, int cl = 0, int cr = n - 1) { pushtag(cv); if(cl > cr || cl > qr || cr < ql) return MP(1e9, 1e9); if(ql <= cl && cr <= qr) return dat[cv]; int mid = cl + cr >> 1; PII L = query(ql, qr, cv << 1 | 0, cl, mid); PII R = query(ql, qr, cv << 1 | 1, mid + 1, cr); pull(cv); return min(L, R); } void update(int l, int r, int v) { l %= n; l = (l + n) % n; r %= n; r = (r + n) % n; if(l <= r) modify(l, r, v); else modify(0, r, v), modify(l, n - 1, v); } PII get(int l, int r) { l %= n; l = (l + n) % n; r %= n; r = (r + n) % n; if(l <= r) return query(l, r); else return min(query(0, r), query(l, n - 1)); } } tre; struct segt1 { PII dat[4000005]; void build(int cv = 1, int cl = 1, int cr = n) { dat[cv] = MP(-1, -1); if(cl == cr) return; int mid = cl + cr >> 1; build(cv << 1, cl, mid); build(cv << 1 | 1, mid + 1, cr); } void modify(int idx, PII v, int cv = 1, int cl = 1, int cr = n) { if(cl == cr) { dat[cv] = v; return; } int mid = cl + cr >> 1; if(idx <= mid) modify(idx, v, cv << 1, cl, mid); else modify(idx, v, cv << 1 | 1, mid + 1, cr); dat[cv] = max(dat[cv << 1], dat[cv << 1 | 1]); } PII query(int ql, int qr, int cv = 1, int cl = 1, int cr = n) { if(cl > cr || cl > qr || cr < ql) return MP(-1, -1); if(ql <= cl && cr <= qr) return dat[cv]; int mid = cl + cr >> 1; return max(query(ql, qr, cv << 1, cl, mid), query(ql, qr, cv << 1 | 1, mid + 1, cr)); } } tre1; vector<int> ord; void go(int x) { while(tre.get(x - (k - 1), x - 1).first == 0) go(tre.get(x - (k - 1), x - 1).second); tre.update(x - (k - 1), x, 1); tre.update(x, x, -1e9); ord.push_back(x); } int dis(int i, int j) { return i > j ? n - i + j : j - i; } void init(int k, vector<int> r) { n = (int) r.size(); ::k = k; rep(i, n) h[i] = r[i]; tre.build(); while(ord.size() < n) go(tre.dat[1].second); rep(i, n) h[ord[i]] = n - i; rep(i, n) h[i + n] = h[i]; n *= 2; tre1.build(); rep(i, n) { if(i - k >= 0) tre1.modify(h[i - k], MP(-1, -1)); jumpL[i][0] = tre1.query(1, h[i] - 1).second; tre1.modify(h[i], MP(h[i], i)); } tre1.build(); for(int i = n - 1; i >= 0; i --) { if(i + k < n) tre1.modify(h[i + k], MP(-1, -1)); jumpR[i][0] = tre1.query(1, h[i] - 1).second; tre1.modify(h[i], MP(h[i], i)); } rep1(j, 24) rep(i, n) jumpL[i][j] = (jumpL[i][j - 1] == -1 ? -1 : jumpL[jumpL[i][j - 1]][j - 1]); rep1(j, 24) rep(i, n) jumpR[i][j] = (jumpR[i][j - 1] == -1 ? -1 : jumpR[jumpR[i][j - 1]][j - 1]); } /*bool cmp(int i, int j) { if(jump[i][0] == -1) return false; int L = ; for(int k = 24; k >= 0; k--) { if(jump[i][k] != -1 && ) } if(dis(i, j) >= k && jump[i][0] != -1) i = jump[i][0]; return (dis(i, j) < k && h[i] > h[j]); }*/ bool cmpR(int i, int j) { for(int k = 24; k >= 0; k --) if(jumpR[i][k] != -1 && jumpR[i][k] < j) i = jumpR[i][k]; return (j - i < k && h[i] > h[j]); } bool cmpL(int i, int j) { for(int k = 24; k >= 0; k --) if(jumpL[i][k] != -1 && jumpL[i][k] > j) i = jumpL[i][k]; return (i - j < k && h[i] > h[j]); } int compare_plants(int x, int y) { if(x > y) return -compare_plants(x, y); if(cmpR(x, y)) return 1; if(cmpR(y, x + n / 2)) return -1; if(cmpL(y, x)) return -1; if(cmpL(x + n / 2, y)) return 1; return 0; } /* 4 3 2 0 1 1 2 0 2 1 2 4 2 2 0 1 0 1 0 3 1 3 */

Compilation message (stderr)

plants.cpp: In member function 'void segt::build(int, int, int)':
plants.cpp:31:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
plants.cpp: In member function 'void segt::modify(int, int, int, int, int, int)':
plants.cpp:39:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
plants.cpp: In member function 'PII segt::query(int, int, int, int, int)':
plants.cpp:49:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
plants.cpp: In member function 'void segt1::build(int, int, int)':
plants.cpp:74:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
plants.cpp: In member function 'void segt1::modify(int, PII, int, int, int)':
plants.cpp:80:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
plants.cpp: In member function 'PII segt1::query(int, int, int, int, int)':
plants.cpp:88:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:106:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |  while(ord.size() < n) go(tre.dat[1].second);
      |        ~~~~~~~~~~~^~~
plants.cpp:3:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    3 | #define rep(i, n) for(int i = 0; i < (int)(n); i ++)
      |                   ^~~
plants.cpp:108:2: note: in expansion of macro 'rep'
  108 |  rep(i, n) h[i + n] = h[i]; n *= 2;
      |  ^~~
plants.cpp:108:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  108 |  rep(i, n) h[i + n] = h[i]; n *= 2;
      |                             ^
#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...