#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 2e5 + 10;
const int lg = 20;
const int inf = 1e6;
int n, k, a[maxn], idx[maxn], ver[maxn], seg[maxn << 2][3], lazy[maxn << 2][3];
ll par[2][maxn][lg];
void shift(int v, int x, int l, int r);
void add(int v, int x, int l, int r, int ql, int qr, int val){
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr){
seg[v][x] += val;
lazy[v][x] += val;
return;
}
shift(v, x, l, r);
int mid = (l + r) >> 1;
add(v << 1, x, l, mid, ql, qr, val);
add(v << 1 | 1, x, mid, r, ql, qr, val);
seg[v][x] = min(seg[v<<1][x], seg[v<<1|1][x]);
}
int find0(int v, int x, int l, int r){
if (seg[v][x] != 0) return -1;
if (l + 1 == r) return l;
shift(v, x, l, r);
int mid = (l + r) >> 1;
int res = find0(v << 1, x, l, mid);
if (res == -1) return find0(v << 1 | 1, x, mid, r);
return res;
}
void shift(int v, int x, int l, int r){
if (lazy[v][x] == 0) return;
int mid = (l + r) >> 1;
add(v << 1, x, l, mid, l, mid, lazy[v][x]);
add(v << 1 | 1, x, mid, r, mid, r, lazy[v][x]);
lazy[v][x] = 0;
}
int get(int v, int x, int l, int r, int ql, int qr){
if (qr <= l || r <= ql) return inf;
if (ql <= l && r <= qr) return seg[v][x];
shift(v, x, l, r);
int mid = (l + r) >> 1;
return min(get(v << 1, x, l, mid, ql, qr)
, get(v << 1 | 1, x, mid, r, ql, qr));
}
void init(int _k, std::vector<int> r) {
n = r.size();
k = _k;
for (int i = 0; i < n; i++){
a[i] = r[i];
add(1, 0, 0, n, i, i+1, a[i]);
add(1, 1, 0, n, i, i+1, a[i]);
add(1, 2, 0, n, i, i+1, inf);
}
vector<int> topol;
for (int rng = 0; rng < n; rng++){
int tmp;
while((tmp = find0(1, 1, 0, n)) != -1){
add(1, 0, 0, n, tmp+1, tmp+k, 1);
if (tmp+k > n){
add(1, 0, 0, n, 0, tmp+k-n, 1);
}
add(1, 1, 0, n, tmp, tmp+1, inf);
}
tmp = find0(1, 0, 0, n);
add(1, 0, 0, n, tmp+1, tmp+k, -1);
if (tmp+k > n){
add(1, 0, 0, n, 0, tmp+k-n, -1);
}
add(1, 0, 0, n, tmp-k+1, tmp, -1);
add(1, 1, 0, n, tmp-k+1, tmp, -1);
if (tmp-k+1 < 0){
add(1, 0, 0, n, tmp-k+1+n, n, -1);
add(1, 1, 0, n, tmp-k+1+n, n, -1);
}
int mn1 = get(1, 2, 0, n, tmp+1, tmp+k);
int mn2 = get(1, 2, 0, n, tmp-k+1, tmp);
if (tmp+k > n){
mn1 = min(mn1, get(1, 2, 0, n, 0, tmp+k-n));
}
if (tmp-k+1 < 0){
mn2 = min(mn2, get(1, 2, 0, n, tmp-k+1+n, n));
}
if (mn1 != inf){
// debug(tmp, ver[mn1]);
par[0][tmp][0] = (ver[mn1]-tmp+n) % n;
for (int i = 1; i < lg; i++){
par[0][tmp][i] = par[0][tmp][i-1] + par[0][(tmp+par[0][tmp][i-1])%n][i-1];
// debug(i, par[0][tmp][i]);
}
}
if (mn2 != inf){
// debug(tmp, ver[mn2]);
par[1][tmp][0] = (tmp-ver[mn2]+n) % n;
for (int i = 1; i < lg; i++){
par[1][tmp][i] = par[0][tmp][i-1] + par[1][(tmp-par[1][tmp][i-1]+n)%n][i-1];
// debug(i, par[1][tmp][i]);
}
}
ver[n-rng] = tmp;
idx[tmp] = n-rng;
assert(tmp != -1);
add(1, 0, 0, n, tmp, tmp+1, inf);
add(1, 2, 0, n, tmp, tmp+1, (n-rng)-inf);
}
}
bool ok(int x, int y){
// debug(x, y);
int v = x;
int dis = (y - x + n) % n;
// debug(v, dis);
for (int i = lg-1; ~i; i--){
if (par[0][v][i] <= dis){
dis -= par[0][v][i];
v = (v+par[0][v][i]) % n;
}
}
// debug(v);
if (v == y || (idx[y] > idx[v] && dis < k)) return true;
v = x;
dis = (x - y + n) % n;
// debug(v, dis);
for (int i = lg-1; ~i; i--){
if (par[1][v][i] <= dis){
dis -= par[1][v][i];
v = (v-par[1][v][i]+n) % n;
}
}
//debug(v);
if (v == y || (idx[y] > idx[v] && dis < k)) return true;
return false;
}
int compare_plants(int x, int y) {
return (ok(x, y)? -1: (ok(y, x)? 1: 0));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
120 ms |
3812 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
724 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
