#include "plants.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= l; --x)
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;
const int N = 200'010;
const int lg = 20;
ll L[N][lg], R[N][lg];
int val[N], pos[N];
int n, k;
namespace seg1 {
int a[2*N];
void init() { fill(a, a+2*N, N); }
void up(int p, int x) {
p += N;
while (p > 0) {
a[p] = x;
p /= 2;
}
}
int get(int l, int r) {
l += N;
r += N;
int ans = N;
while (l < r) {
if (l&1) ans = min(ans, a[l++]);
if (r&1) ans = min(ans, a[--r]);
l /= 2;
r /= 2;
}
return ans;
}
int getc(int l, int r) {
--r;
l = (l%n+n)%n;
r = (r%n+n)%n;
++r;
if (l >= r)
return min(get(0, r), get(l, n));
else
return get(l, r);
}
}
namespace seg2 {
struct node {
int mn;
int lzy;
int l, r;
pii mxdif;
} t[N*4];
int sz;
void merge(int i) {
node &v = t[i], &l = t[2*i+1], &r = t[2*i+2];
if (l.mn == r.mn) {
v.mn = l.mn;
v.l = l.l;
v.r = r.r;
v.mxdif = max(l.mxdif, r.mxdif);
v.mxdif = max(v.mxdif, pii{r.l - l.r, r.l});
} else {
node &u = l.mn < r.mn? l: r;
v = u;
v.lzy = 0;
}
}
void tag(int i, int x) { t[i].mn += x; t[i].lzy += x; }
void ppg(int i) {
if (t[i].lzy) {
tag(2*i+1, t[i].lzy);
tag(2*i+2, t[i].lzy);
t[i].lzy = 0;
}
}
void init(const vector<int> &vec, int i, int b, int e) {
if (e-b == 1) {
t[i].mn = vec[b];
t[i].l = t[i].r = b;
t[i].mxdif = {-1, -1};
return;
}
init(vec, 2*i+1, b, (b+e)/2);
init(vec, 2*i+2, (b+e)/2, e);
merge(i);
}
void init(const vector<int> &vec) { sz = vec.size(); init(vec, 0, 0, sz); }
void add(int l, int r, int x, int i, int b, int e) {
if (l <= b && e <= r)
return tag(i, x);
if (r <= b || e <= l)
return;
ppg(i);
add(l, r, x, 2*i+1, b, (b+e)/2);
add(l, r, x, 2*i+2, (b+e)/2, e);
merge(i);
}
void add(int l, int r, int x) { add(l, r, x, 0, 0, sz); }
void addc(int l, int r, int x) {
--r;
l = (l%n+n)%n;
r = (r%n+n)%n;
++r;
if (l >= r) {
add(0, r, x);
add(l, sz, x);
} else {
add(l, r, x);
}
}
int get() {
if (t[0].mxdif.first >= k)
return t[0].mxdif.second;
else
return t[0].l;
}
}
void init(int k, std::vector<int> r) {
::k = k;
n = r.size();
seg2::init(r);
LoopR (x,0,n) {
int p = seg2::get();
seg2::addc(p-k+1, p, -1);
seg2::add(p, p+1, N);
val[p] = x;
pos[x] = p;
//cerr << p << "-\n";
}
seg1::init();
LoopR (i,0,n) {
int l = seg1::getc(pos[i]-k+1, pos[i]);
int r = seg1::getc(pos[i]+1, pos[i]+k);
seg1::up(pos[i], i);
L[pos[i]][0] = l == N? 0: (pos[i]-pos[l]+n)%n;
R[pos[i]][0] = r == N? 0: (pos[r]-pos[i]+n)%n;
}
Loop (j,0,lg-1) {
Loop (i,0,n) {
int l = ((i - L[i][j])%n+n)%n;
int r = ((i + R[i][j])%n+n)%n;
L[i][j+1] = L[i][j] + L[l][j];
R[i][j+1] = R[i][j] + R[r][j];
}
}
//Loop (i,0,n)
// cerr << L[i][0] << ' ';
//cerr << '\n';
//Loop (i,0,n)
// cerr << R[i][0] << ' ';
//cerr << '\n';
}
bool try_left(int x, int y)
{
ll dis = 0;
while (L[x][0]) {
x = ((x - L[x][0])%n+n)%n;
if (val[x] > val[y])
break;
dis += L[x][0];
}
//LoopR (i,0,lg) {
// int x2 = ((x - L[x][i])%n+n)%n;
// if (val[x2] <= val[y]) {
// dis += L[x][i];
// x = x2;
// }
//}
return (x-y+n)%n <= dis;
}
bool try_right(int x, int y)
{
ll dis = 0;
while (R[x][0]) {
x = ((x + R[x][0])%n+n)%n;
if (val[x] > val[y])
break;
dis += L[x][0];
}
//LoopR (i,0,lg) {
// int x2 = ((x + R[x][i])%n+n)%n;
// if (val[x2] <= val[y]) {
// dis += R[x][i];
// x = x2;
// }
//}
return (y-x+n)%n <= dis;
}
bool try_lr(int x, int y) { return try_left(x, y) || try_right(x, y); }
int compare_plants(int x, int y) {
if (val[x] < val[y]) {
if (try_lr(x, y))
return -1;
else
return 0;
} else {
if (try_lr(y, x))
return 1;
else
return 0;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
20564 KB |
Output is correct |
| 2 |
Correct |
9 ms |
20592 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
20624 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
20616 KB |
Output is correct |
| 2 |
Correct |
10 ms |
20564 KB |
Output is correct |
| 3 |
Correct |
9 ms |
20564 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
20564 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
20616 KB |
Output is correct |
| 2 |
Correct |
10 ms |
20564 KB |
Output is correct |
| 3 |
Correct |
9 ms |
20564 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
20564 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
20564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
20596 KB |
Output is correct |
| 2 |
Correct |
8 ms |
20564 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
20632 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
20564 KB |
Output is correct |
| 2 |
Correct |
9 ms |
20564 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
20564 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
20564 KB |
Output is correct |
| 2 |
Correct |
9 ms |
20592 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
20624 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
