#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "plants.h"
struct MINARGSEGTREE {
int n;
VPI tree;
VI lazy;
MINARGSEGTREE(){}
MINARGSEGTREE(int sz) {
n = 1;
while (n < sz) n *= 2;
tree = VPI(2*n, {+1e9, -1});
lazy = VI(2*n);
}
void push(int N) {
tree[N].ff += lazy[N];
if (2*N+2 < 2*n) {
lazy[2*N+1] += lazy[N];
lazy[2*N+2] += lazy[N];
}
lazy[N] = 0;
}
void set(int N, int L, int R, int i, PII s) {
push(N);
if (i < L || i > R) return;
if (L == R) {
tree[N] = s;
return;
}
int M = (L + R) / 2;
set(2*N+1, L, M, i, s);
set(2*N+2, M+1, R, i, s);
tree[N] = min(tree[2*N+1], tree[2*N+2]);
}
void add(int N, int L, int R, int l, int r, int s) {
push(N);
if (R < l || L > r) return;
if (l <= L && R <= r) {
lazy[N] = s;
push(N);
return;
}
int M = (L + R) / 2;
add(2*N+1, L, M, l, r, s);
add(2*N+2, M+1, R, l, r, s);
tree[N] = min(tree[2*N+1], tree[2*N+2]);
}
PII get(int N, int L, int R, int l, int r) {
push(N);
if (l <= L && R <= r) return tree[N];
if (R < l || L > r) return {+1e9, -1};
int M = (L + R) / 2;
return min(get(2*N+1, L, M, l, r), get(2*N+2, M+1, R, l, r));
}
void set(int i, int s) {
set(0, 0, n-1, i, {s, i});
}
void add(int l, int r, int s) {
add(0, 0, n-1, l, r, s);
}
PII get(int l, int r) {
return get(0, 0, n-1, l, r);
}
};
struct FIRSTZERODS {
int n;
MINARGSEGTREE seg;
FIRSTZERODS(){}
FIRSTZERODS(VI a) {
n = a.size();
seg = MINARGSEGTREE(n);
rep(i, n) seg.set(i, a[i]);
}
void remove(int i) {
seg.set(i, +1e9);
}
void decrement(int l, int r) {
l = (l+100*n)%n;
r = (r+100*n)%n;
if (l <= r) seg.add(l, r, -1);
else {
seg.add(l, n-1, -1);
seg.add(0, r, -1);
}
}
int get(int l, int r) {
l = (l+100*n)%n;
r = (r+100*n)%n;
PII ret;
if (l <= r) ret = seg.get(l, r);
else {
ret = seg.get(l, n-1);
if (ret.ff) ret = seg.get(0, r);
}
if (ret.ff == 0) return ret.ss;
return -1;
}
void print() {
rep(i, n) cout << seg.get(i, i).ff << " "; cout << endl;
}
};
int n, k;
FIRSTZERODS seg;
VI a;
int mx;
VVI gp;
void extract(int i) {
while (true) {
int prev = seg.get(i-k+1, i-1);
if (prev == -1) break;
extract(prev);
}
a[i] = mx--;
seg.remove(i);
seg.decrement(i-k+1, i-1);
}
VI b;
VI pr, pl;
void init(int K_ARG, VI r) {
k = K_ARG;
n = r.size();
seg = FIRSTZERODS(r);
a = VI(n, -1);
mx = n-1;
while (mx >= 0) extract(seg.get(0, n-1));
if (n <= 300) {
gp = VVI(n, VI(n));
rep(i, n) replr(jwm, i+1, i+k-1) {
int j = jwm%n;
if (a[j] > a[i]) gp[i][j] = true;
else gp[j][i] = true;
}
rep(m, n) rep(u, n) rep(v, n) {
gp[u][v] |= gp[u][m] && gp[m][v];
}
}
rep(_, 3) for (int x : a) b.pb(x);
pr = pl = VI(3*n);
rep(i, 3*n) pr[i] = pl[i] = i;
set<PII> st;
replr(i, 0, k-1) st.insert({b[i], i});
replr(i, 0, 3*n-1) {
auto it = st.upper_bound({b[i], +2e9});
if (it != st.end()) pr[i] = it->ss;
st.erase({b[i], i});
if (i+k < 3*n) st.insert({b[i+k], i+k});
}
st = set<PII>();
reprl(i, 3*n-1, 3*n-k) st.insert({b[i], i});
reprl(i, 3*n-1, 0) {
auto it = st.upper_bound({b[i], +2e9});
if (it != st.end()) pl[i] = it->ss;
st.erase({b[i], i});
if (i-k >= 0) st.insert({b[i-k], i-k});
}
/*rep(i, 3*n) cout << i << "\t"; cout << endl;*/
/*for (int x : b) cout << x << " "; cout << endl;*/
/*for (int x : pr) cout << x << " "; cout << endl;*/
/*for (int x : pl) cout << x << " "; cout << endl;*/
}
bool goright(int x, int y) {
/*cout << "goright(" << x << ", " << y << ")" << endl;*/
while (pr[x] < y) {
if (x == pr[x]) break;
x = pr[x];
}
/*cout << "AMENAVERJIN INDEX@ " << x << endl;*/
return y <= x+k-1 && b[y] > b[x];
}
bool goleft(int x, int y) {
/*cout << "goleft(" << x << ", " << y << ")" << endl;*/
while (pl[x] > y) {
if (x == pr[x]) break;
x = pl[x];
}
return x <= y+k-1 && b[y] > b[x];
}
bool issmaller(int x, int y) {
if (y > x) return goright(x, y) || goleft(x, y-n);
return goright(x, y+n) || goleft(x, y);
}
int compare_plants(int x, int y) {
x += n;
y += n;
if (issmaller(x, y)) return -1;
if (issmaller(y, x)) return +1;
return 0;
if (n <= 300) {
if (gp[y][x]) return +1;
if (gp[x][y]) return -1;
return 0;
}
if (a[x] > a[y]) return +1;
if (a[x] < a[y]) return -1;
return 0;
}
Compilation message
plants.cpp: In member function 'void FIRSTZERODS::print()':
plants.cpp:9:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
9 | #define rep(i, n) for (int i = 0; i < int(n); ++i)
| ^~~
plants.cpp:129:9: note: in expansion of macro 'rep'
129 | rep(i, n) cout << seg.get(i, i).ff << " "; cout << endl;
| ^~~
plants.cpp:129:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
129 | rep(i, n) cout << seg.get(i, i).ff << " "; cout << endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Execution timed out |
4099 ms |
348 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Execution timed out |
4091 ms |
348 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Execution timed out |
4091 ms |
348 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
105 ms |
5040 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
360 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Execution timed out |
4094 ms |
348 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Execution timed out |
4096 ms |
348 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Execution timed out |
4099 ms |
348 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
