| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 936434 | EJIC_B_KEDAX | Comparing Plants (IOI20_plants) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "plants.h"
#define x first
#define y second
using ll = long long;
using namespace std;
#define int ll
const int LG = 18, N = 1 << LG;
int st1[2 * N], st2[2 * N], lz1[2 * N], lz2[2 * N], timer = 1, fndl[2 * N], fndl2[2 * N], used3[N], level[N], kk, nn;
pair<int, int> fnd[2 * N], fnd2[2 * N];
pair<int, ll> binupr[LG][N], binupl[LG][N];
void push(int i, int st[], int lz[]) {
if (lz[i] != -1) {
st[2 * i + 1] = lz[i];
st[2 * i + 2] = lz[i];
lz[2 * i + 1] = lz[i];
lz[2 * i + 2] = lz[i];
lz[i] = -1;
}
}
void set_seg(int l, int r, int x, int st[], int lz[], int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 >= l && r1 <= r) {
st[i] = x;
lz[i] = x;
return;
}
if (l1 > r || r1 < l) {
return;
}
push(i, st, lz);
set_seg(l, r, x, st, lz, l1, (l1 + r1) / 2, 2 * i + 1);
set_seg(l, r, x, st, lz, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
st[i] = min(st[2 * i + 1], st[2 * i + 2]);
}
int get(int ind, int st[], int lz[], int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 == ind && r1 == ind) {
return st[i];
}
if (l1 > ind || r1 < ind) {
return INT32_MAX;
}
push(i, st, lz);
return min(get(ind, st, lz, l1, (l1 + r1) / 2, 2 * i + 1), get(ind, st, lz, (l1 + r1) / 2 + 1, r1, 2 * i + 2));
}
void push(int i) {
fnd[2 * i + 1].x += fndl[i];
fnd[2 * i + 2].x += fndl[i];
fndl[2 * i + 1] += fndl[i];
fndl[2 * i + 2] += fndl[i];
fndl[i] = 0;
}
void push1(int i) {
fnd2[2 * i + 1].x += fndl2[i];
fnd2[2 * i + 2].x += fndl2[i];
fndl2[2 * i + 1] += fndl2[i];
fndl2[2 * i + 2] += fndl2[i];
fndl2[i] = 0;
}
void add_seg(int l, int r, int x, int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 >= l && r1 <= r) {
fnd[i].x += x;
fndl[i] += x;
return;
}
if (l1 > r || r1 < l) {
return;
}
push(i);
add_seg(l, r, x, l1, (l1 + r1) / 2, 2 * i + 1);
add_seg(l, r, x, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
fnd[i] = min(fnd[2 * i + 1], fnd[2 * i + 2]);
}
pair<int, int> get_min(int l, int r, int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 >= l && r1 <= r) {
return fnd[i];
}
if (l1 > r || r1 < l) {
return {INT32_MAX, -1};
}
push(i);
return min(get_min(l, r, l1, (l1 + r1) / 2, 2 * i + 1), get_min(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 2));
}
void add_seg1(int l, int r, int x, int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 >= l && r1 <= r) {
fnd2[i].x += x;
fndl2[i] += x;
return;
}
if (l1 > r || r1 < l) {
return;
}
push1(i);
add_seg1(l, r, x, l1, (l1 + r1) / 2, 2 * i + 1);
add_seg1(l, r, x, (l1 + r1) / 2 + 1, r1, 2 * i + 2);
fnd2[i] = min(fnd2[2 * i + 1], fnd2[2 * i + 2]);
}
pair<int, int> get_min1(int l, int r, int l1 = 0, int r1 = N - 1, int i = 0) {
if (l1 >= l && r1 <= r) {
return fnd2[i];
}
if (l1 > r || r1 < l) {
return {INT32_MAX, -1};
}
push1(i);
return min(get_min1(l, r, l1, (l1 + r1) / 2, 2 * i + 1), get_min1(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 2));
}
void init(int k, vector<int> r) {
kk = k;
int n = r.size();
nn = n;
int ok = 0;
for (int i = 0; i < 2 * N; i++) {
st1[i] = -1;
st2[i] = -1;
lz1[i] = -1;
lz2[i] = -1;
}
for (int i = 0; i < N; i++) {
fnd[i + N - 1].y = i;
fnd2[i + N - 1].y = i;
level[i] = n;
}
for (int i = 0; i < n; i++) {
add_seg(i, i, r[i]);
add_seg1(i, i, r[i]);
if (r[i] == 0) {
used3[i] = 1;
if (i + k > n) {
add_seg(i + 1, n - 1, 1);
add_seg(0, i + k - n - 1, 1);
} else {
add_seg(i + 1, i + k - 1, 1);
}
}
}
while (ok < n) {
auto [value, i] = get_min(0, n - 1);
if (value) {
exit(1);
}
int tmp1 = get(i, st1, lz1), tmp2 = get(i, st2, lz2);
if (tmp1 != -1) {
level[i] = min(level[i], level[tmp1] - 1);
}
if (tmp2 != -1) {
level[i] = min(level[i], level[tmp2] - 1);
}
vector<int> z;
if (i + k - 1 < n) {
set_seg(i + 1, i + k - 1, i, st2, lz2);
add_seg(i + 1, i + k - 1, -1);
} else {
set_seg(i + 1, n - 1, i, st2, lz2);
set_seg(0, i + k - 1 - n, i, st2, lz2);
add_seg(i + 1, n - 1, -1);
add_seg(0, i + k - 1 - n, -1);
}
if (i >= k - 1) {
add_seg(i - k + 1, i - 1, -1);
add_seg1(i - k + 1, i - 1, -1);
int left = i - k + 1;
while (left <= i - 1 && !get_min1(left, i - 1).x) {
z.push_back(get_min1(left, i - 1).y);
assert(left <= z.back());
left = z.back() + 1;
}
set_seg(i - k + 1, i - 1, i, st1, lz1);
} else {
add_seg(0, i - 1, -1);
add_seg1(0, i - 1, -1);
set_seg(0, i - 1, i, st1, lz1);
add_seg(n + 1 - k + i, n - 1, -1);
add_seg1(n + 1 - k + i, n - 1, -1);
set_seg(n + 1 - k + i, n - 1, i, st1, lz1);
int left = 0;
while (left <= i - 1 && !get_min1(left, i - 1).x) {
z.push_back(get_min1(left, i - 1).y);
assert(left <= z.back());
left = z.back() + 1;
}
left = n + 1 - k + i;
while (left <= n - 1 && !get_min1(left, n - 1).x) {
z.push_back(get_min1(left, n - 1).y);
assert(left <= z.back());
left = z.back() + 1;
}
}
for (int j : z) {
if (!used3[j]) {
if (j + k > n) {
add_seg(j + 1, n - 1, 1);
add_seg(0, j + k - n - 1, 1);
} else {
add_seg(j + 1, j + k - 1, 1);
}
used3[j] = 1;
}
}
add_seg(i, i, INT32_MAX / 2);
add_seg1(i, i, INT32_MAX / 2);
ok++;
}
set<pair<int, int>> st1;
set<pair<int, int>> st2;
for (int i = n - k + 1; i < n; i++) {
st1.emplace(-level[i], i);
}
for (int i = 1; i < k; i++) {
st2.emplace(-level[i], i);
}
for (int i = 0; i < n; i++) {
auto lb1 = st1.lower_bound({-level[i], N});
if (lb1 == st1.end()) {
binupl[0][i].x = i;
} else {
binupl[0][i].x = (*lb1).y;
}
st1.erase({-level[(i - k + 1 + n) % n], (i - k + 1 + n) % n});
st1.emplace(-level[i], i);
binupl[0][i].y = i - binupl[0][i].x;
if (binupl[0][i].y < 0) {
binupl[0][i].y += n;
}
auto lb2 = st2.lower_bound({-level[i], N});
if (lb2 == st2.end()) {
binupr[0][i].x = i;
} else {
binupr[0][i].x = (*lb2).y;
}
st2.erase({-level[i + 1], i + 1});
st2.emplace(-level[(i + k) % n], (i + k) % n);
binupr[0][i].y = binupr[0][i].x - i;
if (binupr[0][i].y < 0) {
binupr[0][i].y += n;
}
}
for (int l = 1; l < LG; l++) {
for (int i = 0; i < n; i++) {
binupl[l][i].x = binupl[l - 1][binupl[l - 1][i].x].x;
binupr[l][i].x = binupr[l - 1][binupr[l - 1][i].x].x;
binupl[l][i].y = binupl[l - 1][binupl[l - 1][i].x].y + binupl[l - 1][i].y;
binupr[l][i].y = binupr[l - 1][binupr[l - 1][i].x].y + binupr[l - 1][i].y;
}
}
for (int i = 0; i < n; i++) {
for (int l = 0; l < 1; l++) {
assert(binupl[l][i].y < n);
assert(binupr[l][i].y < n);
}
}
}
bool try_compare(int x, int y) {
ll dist = x - y;
int nw = x;
if (dist < 0) {
dist += nn;
}
dist -= kk - 1;
if (dist <= 0) {
return true;
}
for (int i = LG - 1; i >= 0; i--) {
if (binupl[i][nw].y < dist) {
dist -= binupl[i][nw].y;
nw = binupl[i][nw].x;
}
}
assert(dist > 0);
dist -= binupl[0][nw].y;
nw = binupl[0][nw].x;
if (level[nw] >= level[y] && dist <= 0) {
return true;
}
dist = y - x, nw = x;
if (dist < 0) {
dist += nn;
}
dist -= kk - 1;
if (dist <= 0) {
return true;
}
for (int i = LG - 1; i >= 0; i--) {
if (binupr[i][nw].y < dist) {
dist -= binupr[i][nw].y;
nw = binupr[i][nw].x;
}
}
assert(dist > 0);
dist -= binupr[0][nw].y;
nw = binupr[0][nw].x;
if (level[nw] >= level[y] && dist <= 0) {
return true;
}
return false;
}
int compare_plants(int x, int y) {
if (try_compare(x, y) && level[x] > level[y]) {
return 1;
}
if (try_compare(y, x) && level[y] > level[x]) {
return -1;
}
return 0;
}
#undef int