#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5 + 5;
int n, k;
struct segtree {
int l, r, lz = 0;
segtree* lc = 0, * rc = 0;
int mn = 0, lz = 0;
segtree() : segtree(-1, -1) {};
segtree(int l, int r) : l(l), r(r) {
if (l == r)return;
int m = (l + r) / 2;
lc = getmem(); *lc = segtree(l, m);
rc = getmem(); *rc = segtree(m + 1, r);
}
void apply(int v) {
mn += v; lz += v;
}
void push() {
if (l == r) return;
lc->apply(lz);rc->apply(lz);
lz = 0;
}
void pull() {
if (l == r) return;
mn = min(lc->mn, rc->mn) + lz;
}
void upd(int ql, int qr, int qv) {
if (qr < 0) { ql += n; qr += n; }
if (ql < 0) {
upd(0, qr, qv);
upd((n)+ql, (n - 1), qv);
}
if (ql >= n) { ql -= n; qr -= n; }
if (qr >= n) {
upd(ql, (n - 1), qv);
upd(0, qr - (n), qv);
return;
}
if (l > qr || r < ql) return;
if (ql <= l && r <= qr) { apply(qv); return; }
push();
lc->upd(ql, qr, qv);
rc->upd(ql, qr, qv);
pull();
}
int extract_min() {
if (l == r) return l;
push();
if (lc->mn == min) return lc->extract_min();
return rc->extract_min();
}
}mem[mx * 8]; int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }
const int inf = 1e9 + 7;
namespace rmq {
struct segtree {
int l, r, lz = 0;
segtree* lc = 0, * rc = 0;
pair<int, int> v = { 0, -1 };
segtree() : segtree(-1, -1) {};
segtree(int l, int r) : l(l), r(r) {
if (l == r)return;
int m = (l + r) / 2;
lc = getmem(); *lc = segtree(l, m);
rc = getmem(); *rc = segtree(m + 1, r);
}
void upd(int qi, int qv) {
if (l == r) { v = { qv, qi };return; }
if (qi <= lc->r) lc->upd(qi, qv);
else rc->upd(qi, qv);
v = min(lc->v, rc->v);
}
pair<int, int> q(int ql, int qr) {
if (qr < 0) { ql += n; qr += n; }
if (ql < 0) {
return min(q(0, qr), q((n)+ql, (n - 1)));
}
if (ql >= n) { ql -= n; qr -= n; }
if (qr >= n) {
return min(q(ql, (n - 1)), q(0, qr - (n), qv));
}
if (l > qr || r < ql)return { 0, -1 };
if (ql <= l && r <= qr) return v;
return min(lc->q(ql, qr), rc->q(ql, qr));
}
}mem[mx * 4]; int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }
}
vector<int> time(n), rtime(n);
int parl[mx][20], parr[mx][20];
void init(int kk, std::vector<int> r) {
n = r.size();k = kk;k--;
segtree parta(0, n - 1), partb(0, n - 1); partb.upd(0, n - 1, 1);
for (int i = 0; i < n; i++) parta.upd(i, i, r[i]);
for (int i = 0; i < n; i++) {
while (parta.mn == 0) {
int t = parta.extract_min();
parta.upd(t, t, mx);
partb.upd(t, t, -1);
partb.upd(t + 1, t + k, 1);
}
assert(partb.min == 0);
int t = partb.extract_min();
time[t] = i;
rtime[i] = t;
partb.upd(t + 1, t + k, -1);
parta.upd(t - k, t, -1);
}
rmg::segtree tim(0, n - 1);
for (int i = 0; i < n; i++) {
int t = tim.q(rtime[i] - k, rtime[i]).second;
if (t == -1) parl[i][0] = i;
else parl[i][0] = t;
t = tim.q(rtime[i], rtime[i] + k);
if (t == -1) parr[i][0] = i;
else parr[i][0] = t;
}
for (int i = 1; i < 20; i++) {
for (int j = 0; j < n; j++) {
if (parl[j][0] > j) parl[j][i] = parl[j][i - 1];
else if (parl[parl[j][i - 1]][i - 1] > j) parl[j][i] = parl[j][i - 1];
else parl[j][i] = parl[parl[j][i - 1]][i - 1];
}
}
for (int i = 1; i < 20; i++) {
for (int j = 0; j < n; j++) {
if (parr[j][0] < j) parr[j][i] = parr[j][i - 1];
else if (parr[parr[j][i - 1]][i - 1] < j) parr[j][i] = parr[j][i - 1];
else parr[j][i] = parr[parr[j][i - 1]][i - 1];
}
}
return;
}
int compare_plants(int x, int y) {
//compare zero
if (x + k >= y || y + k - n >= x) { return time[x] < time[y] ? 1 : -1; }
//compare one
int t = x;
for (int i = 19; i >= 0; i++) {
if (parr[t][i] + k < y) t = parr[t][i];
}
t = parr[t][0];
if (t + k >= y && time[t] > time[y]) return -1;
//compare two
t = parl[x][19];
if (y + k - n >= t && time[y] < time[t]) return -1;
t = parl[t][0];
for (int i = 19; i >= 0; i++) {
if (y + k < parl[t][i]) t = parl[t][i];
}
t = parl[t][0];
if (y + k >= t && time[y] < time[t])return -1;
//compare three
t = y;
for (int i = 19; i >= 0; i++) {
if (x + k < parl[t][i]) t = parl[t][i];
}
t = parl[t][0];
if (x + k >= t && time[t] > time[x]) return 1;
//compare four
t = parr[y][19];
if (t + k - n >= x && time[t] > time[x]) return 1;
t = parr[t][0];
for (int i = 19; i >= 0; i++) {
if (parr[t][i] + k < x) t = parr[t][i];
}
t = parr[t][0];
if (t + k >= x && time[t] > time[x]) return 1;
return 0;
}
Compilation message
plants.cpp:12:22: error: redeclaration of 'int segtree::lz'
12 | int mn = 0, lz = 0;
| ^
plants.cpp:10:15: note: previous declaration 'int segtree::lz'
10 | int l, r, lz = 0;
| ^~
plants.cpp: In constructor 'segtree::segtree(int, int)':
plants.cpp:17:14: error: 'getmem' was not declared in this scope; did you mean 'memmem'?
17 | lc = getmem(); *lc = segtree(l, m);
| ^~~~~~
| memmem
plants.cpp: In member function 'int segtree::extract_min()':
plants.cpp:54:20: error: invalid operands of types 'int' and '<unresolved overloaded function type>' to binary 'operator=='
54 | if (lc->mn == min) return lc->extract_min();
| ~~~~~~~^~~~~~
plants.cpp: At global scope:
plants.cpp:58:10: error: no declaration matches 'segtree* segtree::getmem()'
58 | segtree* segtree::getmem() { return &mem[memsz++]; }
| ^~~~~~~
plants.cpp:58:10: note: no functions named 'segtree* segtree::getmem()'
plants.cpp:9:8: note: 'struct segtree' defined here
9 | struct segtree {
| ^~~~~~~
plants.cpp: In constructor 'rmq::segtree::segtree(int, int)':
plants.cpp:70:18: error: 'getmem' was not declared in this scope; did you mean 'memmem'?
70 | lc = getmem(); *lc = segtree(l, m);
| ^~~~~~
| memmem
plants.cpp: In member function 'std::pair<int, int> rmq::segtree::q(int, int)':
plants.cpp:86:59: error: 'qv' was not declared in this scope; did you mean 'v'?
86 | return min(q(ql, (n - 1)), q(0, qr - (n), qv));
| ^~
| v
plants.cpp: At global scope:
plants.cpp:93:14: error: no declaration matches 'rmq::segtree* rmq::segtree::getmem()'
93 | segtree* segtree::getmem() { return &mem[memsz++]; }
| ^~~~~~~
plants.cpp:93:14: note: no functions named 'rmq::segtree* rmq::segtree::getmem()'
plants.cpp:62:12: note: 'struct rmq::segtree' defined here
62 | struct segtree {
| ^~~~~~~
plants.cpp:97:19: error: 'std::vector<int> time' redeclared as different kind of entity
97 | vector<int> time(n), rtime(n);
| ^
In file included from /usr/include/c++/10/ctime:42,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:49,
from plants.cpp:2:
/usr/include/time.h:75:15: note: previous declaration 'time_t time(time_t*)'
75 | extern time_t time (time_t *__timer) __THROW;
| ^~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from plants.cpp:2:
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:110:22: error: 'struct segtree' has no member named 'min'; did you mean 'mn'?
110 | assert(partb.min == 0);
| ^~~
plants.cpp:112:15: warning: pointer to a function used in arithmetic [-Wpointer-arith]
112 | time[t] = i;
| ^
plants.cpp:112:17: error: assignment of read-only location '*(time + ((sizetype)t))'
112 | time[t] = i;
| ~~~~~~~~^~~
plants.cpp:117:5: error: 'rmg' has not been declared
117 | rmg::segtree tim(0, n - 1);
| ^~~
plants.cpp:119:17: error: 'tim' was not declared in this scope; did you mean 'time'?
119 | int t = tim.q(rtime[i] - k, rtime[i]).second;
| ^~~
| time
plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:145:54: warning: pointer to a function used in arithmetic [-Wpointer-arith]
145 | if (x + k >= y || y + k - n >= x) { return time[x] < time[y] ? 1 : -1; }
| ^
plants.cpp:145:64: warning: pointer to a function used in arithmetic [-Wpointer-arith]
145 | if (x + k >= y || y + k - n >= x) { return time[x] < time[y] ? 1 : -1; }
| ^
plants.cpp:153:29: warning: pointer to a function used in arithmetic [-Wpointer-arith]
153 | if (t + k >= y && time[t] > time[y]) return -1;
| ^
plants.cpp:153:39: warning: pointer to a function used in arithmetic [-Wpointer-arith]
153 | if (t + k >= y && time[t] > time[y]) return -1;
| ^
plants.cpp:157:33: warning: pointer to a function used in arithmetic [-Wpointer-arith]
157 | if (y + k - n >= t && time[y] < time[t]) return -1;
| ^
plants.cpp:157:43: warning: pointer to a function used in arithmetic [-Wpointer-arith]
157 | if (y + k - n >= t && time[y] < time[t]) return -1;
| ^
plants.cpp:163:29: warning: pointer to a function used in arithmetic [-Wpointer-arith]
163 | if (y + k >= t && time[y] < time[t])return -1;
| ^
plants.cpp:163:39: warning: pointer to a function used in arithmetic [-Wpointer-arith]
163 | if (y + k >= t && time[y] < time[t])return -1;
| ^
plants.cpp:171:29: warning: pointer to a function used in arithmetic [-Wpointer-arith]
171 | if (x + k >= t && time[t] > time[x]) return 1;
| ^
plants.cpp:171:39: warning: pointer to a function used in arithmetic [-Wpointer-arith]
171 | if (x + k >= t && time[t] > time[x]) return 1;
| ^
plants.cpp:175:33: warning: pointer to a function used in arithmetic [-Wpointer-arith]
175 | if (t + k - n >= x && time[t] > time[x]) return 1;
| ^
plants.cpp:175:43: warning: pointer to a function used in arithmetic [-Wpointer-arith]
175 | if (t + k - n >= x && time[t] > time[x]) return 1;
| ^
plants.cpp:181:29: warning: pointer to a function used in arithmetic [-Wpointer-arith]
181 | if (t + k >= x && time[t] > time[x]) return 1;
| ^
plants.cpp:181:39: warning: pointer to a function used in arithmetic [-Wpointer-arith]
181 | if (t + k >= x && time[t] > time[x]) return 1;
| ^
