This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
}
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];
}
}
}
int compare_plants(int x, int y) {
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 (stderr)
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |