#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 2e5 + 5;
const int LOG = 20;
#define inf 0x3F3F3F3F
int n;
array<int, 2> p[2][LOG][MXN];
int in[2][MXN], out[2][MXN], tim[2], used[2];
int a[MXN], cnt[MXN], rr[MXN], f[MXN];
array<int, 2> st[MXN << 2];
int lz[MXN << 2];
void build(int l, int r, int x)
{
if (l == r)
{
st[x] = {cnt[l] - rr[l], l};
return;
}
int mid = (l + r) >> 1;
build(l, mid, 2*x);
build(mid + 1, r, 2*x + 1);
st[x] = min(st[2*x], st[2*x + 1]);
}
void relax(int l, int r, int x)
{
if (!lz[x]) return;
st[x][0] += lz[x];
if (l == r)
{
lz[x] = 0;
return;
}
lz[2*x] += lz[x], lz[2*x + 1] += lz[x];
lz[x] = 0;
}
void upd(int l, int r, int x, int lx, int rx, int val)
{
if (lx > rx) return;
relax(l, r, x);
if (l > rx || r < lx) return;
if (l >= lx && r <= rx)
{
lz[x] += val;
relax(l, r, x);
return;
}
int mid = (l + r) >> 1;
upd(l, mid, 2*x, lx, rx, val);
upd(mid + 1, r, 2*x + 1, lx, rx, val);
st[x] = min(st[2*x], st[2*x + 1]);
}
set<int> idx;
set<array<int, 2>> dif;
void ins(int x)
{
idx.insert(x);
if (idx.size() == 1)
{
dif.insert({0, x});
return;
}
auto it = idx.find(x);
auto itl = it, itr = it;
if (it == idx.begin()) itl = prev(idx.end());
else itl = prev(it);
if (next(it) == idx.end()) itr = idx.begin();
else itr = next(it);
dif.erase({(*itr - *itl + n) % n, *itr});
dif.insert({(x - *itl + n) % n, x});
dif.insert({(*itr - x + n) % n, *itr});
}
void ers(int x)
{
if (idx.size() == 1)
{
idx.clear();
dif.clear();
return;
}
auto it = idx.find(x);
auto itl = it, itr = it;
if (it == idx.begin()) itl = prev(idx.end());
else itl = prev(it);
if (next(it) == idx.end()) itr = idx.begin();
else itr = next(it);
dif.erase({(x - *itl + n) % n, x});
dif.erase({(*itr - x + n) % n, *itr});
dif.insert({(*itr - *itl + n) % n, *itr});
idx.erase(it);
}
// 4 3 2
// 0 1 1 2
// 0 2
// 1 2
void init(int k, vector<int> r)
{
n = r.size();
for (int i = 1; i <= (n * 4); i++) st[i] = {inf, -1};
for (int i = 0; i < n; i++) rr[i] = r[i];
for (int i = 0; i < n; i++) cnt[i] = k - 1;
build(0, n - 1, 1);
while (1)
{
array<int, 2> x = st[1];
if (!x[1]) break;
if (!x[0])
{
ins(x[1]);
upd(0, n - 1, 1, x[1], x[1], inf);
}
else break;
}
int cur = 0;
while (!idx.empty())
{
int ind = (*dif.rbegin())[1];
ers(ind);
f[ind] = ++cur;
if (ind - 1 >= 0) upd(0, n - 1, 1, max(ind - k + 1, 0), ind - 1, -1);
if (ind - k + 1 < 0) upd(0, n - 1, 1, (ind - k + 1 + n) % n, n - 1, -1);
// for (int i = (idx[ind] - 1 + n) % n; i != idx[(ind - 1 + sz) % sz]; i = (i - 1 + n) % n)
// {
// if (!f[i]) adj[idx[ind]].push_back(i);
// }
// for (int i = (idx[ind] + 1) % n; i != (idx[ind] + k) % n; i = (i + 1) % n)
// {
// if (!f[i]) adj[idx[ind]].push_back(i);
// }
// for (int i = (idx[ind] - 1 + n) % n; i != (idx[ind] - k + n) % n; i = (i - 1 + n) % n)
// {
// if (!f[i]) adj[idx[ind]].push_back(i);
// cnt[i]--;
// }
// f[idx[ind]] = 1;
while (1)
{
array<int, 2> x = st[1];
if (!x[0])
{
ins(x[1]);
upd(0, n - 1, 1, x[1], x[1], inf);
}
else break;
}
}
set<array<int, 2>> s;
for (int i = 0; i < k; i++) s.insert({f[i], i});
for (int i = n - 1; i >= 0; i--)
{
s.erase({f[(i + k) % n], (i + k) % n});
auto it = s.lower_bound({f[i], i});
if (it != s.end())
{
p[0][0][i] = {(*it)[1], ((*it)[1] - i + n) % n};
}
s.insert({f[i], i});
}
s.clear();
for (int i = n - k; i < n; i++) s.insert({f[i], i});
for (int i = 0; i < n; i++)
{
s.erase({f[(i - k + n) % n], (i - k + n) % n});
auto it = s.lower_bound({f[i], i});
if (it != s.end())
{
p[1][0][i] = {(*it)[1], (i - (*it)[1] + n) % n};
}
s.insert({f[i], i});
}
for (int j = 0; j < 2; j++)
{
for (int i = 1; i < LOG; i++)
{
for (int k = 0; k < n; k++)
{
int par = p[j][i][k][0];
p[j][i][k] = {p[j][i - 1][par][0], p[j][i - 1][par][1] + p[j][i - 1][k][1]};
}
}
}
}
int check(int x, int y)
{
int x1 = x;
int d = (y - x + n) % n;
int res = 0;
for (int i = LOG - 1; i >= 0; i--)
{
if (f[p[0][i][x][0]] <= f[y])
{
res += p[0][i][x][1];
x = p[0][i][x][0];
}
}
if (f[x] <= f[y] && res >= d) return 1;
d = (x - y + n) % n;
res = 0, x = x1;
for (int i = LOG - 1; i >= 0; i--)
{
if (f[p[1][i][x][0]] <= f[y])
{
res += p[1][i][x][1];
x = p[1][i][x][0];
}
}
return (f[x] <= f[y] && res >= d);
}
int compare_plants(int x, int y)
{
// ? x < y
if (check(x, y)) return -1;
if (check(y, x)) return 1;
return 0;
// return (a[x] > a[y] ? 1 : -1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
10844 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 3 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
10844 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 3 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
10844 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 3 |
Incorrect |
49 ms |
14332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
10844 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
10844 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
10844 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
