#include "plants.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 200'000;
const int MAXLG = 20;
int n, k;
int dist(int s, int t) {
if(s <= t) return t - s;
else return t - s + n;
}
struct Ayaya {
set<int> pos;
set<pii> d;
pii find(int x) {
auto itr = pos.upper_bound(x);
if(itr == pos.end()) {
itr = pos.begin();
}
auto itl = pos.lower_bound(x);
if(itl == pos.begin()) {
itl = prev(pos.end());
} else {
itl = prev(itl);
}
return pii(*itl, *itr);
}
void insert(int x) {
if(sz(pos) == 0) {
pos.insert(x);
d.emplace(0, x);
return;
}
int l, r; tie(l, r) = find(x);
d.erase(pii(dist(l, r), r));
d.insert(pii(dist(l, x), x));
d.insert(pii(dist(x, r), r));
pos.insert(x);
}
void erase(int x) {
if(sz(pos) == 1) {
pos.clear(); d.clear();
return;
}
int l, r; tie(l, r) = find(x);
d.erase(pii(dist(l, x), x));
d.erase(pii(dist(x, r), r));
d.insert(pii(dist(l, r), r));
pos.erase(x);
}
int pop() {
int i = prev(d.end())->S;
erase(i);
return i;
}
void out() {
for(auto &i:pos) cerr << i << " ";
cerr << "\n";
for(auto &i:d) cerr << "(" << i.F << ", " << i.S << ") ";
cerr << "\n";
}
} aya;
#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
int add[MAXN * 4 + 10];
pii mn[MAXN * 4 + 10]; // {value, index}
void pull(int id) {
mn[id] = min(mn[L(id)], mn[R(id)]);
mn[id].F += add[id];
}
void build(int id, int l, int r, int *owo) {
add[id] = 0;
if(l == r) {
add[id] = owo[l];
mn[id] = pii(owo[l], l);
return;
}
int m = (l + r) / 2;
build(L(id), l, m, owo);
build(R(id), m + 1, r, owo);
pull(id);
}
void range_add(int id, int l, int r, int L, int R, int val) {
if(L > R) {
range_add(0, 0, n - 1, L, n - 1, val);
range_add(0, 0, n - 1, 0, R, val);
return;
}
if(l >= L && r <= R) {
add[id] += val; mn[id].F += val;
return;
}
int m = (l + r) / 2;
if(L <= m) range_add(L(id), l, m, L, R, val);
if(R > m) range_add(R(id), m + 1, r, L, R, val);
pull(id);
}
pii find_min(int id, int l, int r, int L, int R) {
if(L > R) {
return min(
find_min(0, 0, n - 1, L, n - 1),
find_min(0, 0, n - 1, 0, R)
);
}
if(l >= L && r <= R) return mn[id];
int m = (l + r) / 2;
pii res(n * 8, -1);
if(L <= m) res = min(res, find_min(L(id), l, m, L, R));
if(R > m) res = min(res, find_min(R(id), m + 1, r, L, R));
res.F += add[id];
return res;
}
void kill_all() {
pii res = find_min(0, 0, n - 1, 0, n - 1);
while(res.F == 0) {
aya.insert(res.S);
range_add(0, 0, n - 1, res.S, res.S, n * 888);
res = find_min(0, 0, n - 1, 0, n - 1);
}
}
} seg;
int r[MAXN + 10];
int rk[MAXN + 10];
int pos[MAXN + 10];
int pl[MAXLG + 10][MAXN + 10];
int pr[MAXLG + 10][MAXN + 10];
int sl[MAXLG + 10][MAXN + 10];
int sr[MAXLG + 10][MAXN + 10];
void init(int __k, vector<int> __r) {
k = __k;
n = sz(__r);
For(i, 0, n - 1) r[i] = __r[i];
seg.build(0, 0, n - 1, r);
seg.kill_all();
For(rank, 1, n) {
int idx = aya.pop();
seg.range_add(0, 0, n - 1, (idx + n - k + 1) % n, (idx + n - 1) % n, -1);
seg.kill_all();
rk[idx] = rank;
pos[rank] = idx;
}
seg.build(0, 0, n - 1, rk);
For(rank, 1, n) {
int idx = pos[rank];
pii owo;
owo = seg.find_min(0, 0, n - 1, (idx + n - k + 1) % n, (idx + n - 1) % n);
pl[0][idx] = (owo.F <= n ? owo.S : idx);
owo = seg.find_min(0, 0, n - 1, (idx + 1) % n, (idx + k - 1) % n);
pr[0][idx] = (owo.F <= n ? owo.S : idx);
sl[0][idx] = dist(pl[0][idx], idx);
sr[0][idx] = dist(idx, pr[0][idx]);
seg.range_add(0, 0, n - 1, idx, idx, n * 888);
}
// For(i, 0, n - 1) cerr << rk[i] << " \n"[i == n - 1];
// For(i, 0, n - 1) cerr << pl[i] << " \n"[i == n - 1];
// For(i, 0, n - 1) cerr << sl[i] << " \n"[i == n - 1];
// For(i, 0, n - 1) cerr << pr[i] << " \n"[i == n - 1];
// For(i, 0, n - 1) cerr << sr[i] << " \n"[i == n - 1];
For(j, 1, MAXLG - 1) {
For(i, 0, n - 1) {
pl[j][i] = pl[j - 1][pl[j - 1][i]];
pr[j][i] = pr[j - 1][pr[j - 1][i]];
sl[j][i] = sl[j - 1][i] + sl[j - 1][pl[j - 1][i]];
sr[j][i] = sr[j - 1][i] + sr[j - 1][pr[j - 1][i]];
}
// For(i, 0, n - 1) cerr << sr[i] << " \n"[i == n - 1];
}
}
int compare_plants(int x, int y) {
if(rk[x] > rk[y]) return -compare_plants(y, x);
int d, x2;
// left
d = dist(y, x);
x2 = x;
Forr(i, MAXLG - 1, 0) {
if(d - sl[i][x2] >= 0) {
d -= sl[i][x2];
x2 = pl[i][x2];
}
}
if(d <= sl[0][x2] && rk[x2] < rk[y]) return 1;
// right
d = dist(x, y);
x2 = x;
Forr(i, MAXLG - 1, 0) {
if(d - sr[i][x2] >= 0) {
d -= sr[i][x2];
x2 = pr[i][x2];
}
}
if(d <= sr[0][x2] && rk[x2] < rk[y]) return 1;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
