| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 877768 | Kanon | Comparing Plants (IOI20_plants) | C++14 | 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"
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}
template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
res += static_cast<char>('0' + v[i]);
}
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);
class segtree {
public:
struct node {
// info here
int min_val = 0;
int min_pos = -1;
int ad = 0;
void apply(int l, int r, int v) {
// add parameter above
ad += v;
min_val += v;
if (min_pos == -1) min_pos = l;
}
// segtree beat here
};
node unite(const node &a, const node &b) const {
node res;
res.min_val = min(a.min_val, b.min_val);
if (res.min_val != a.min_val) res.min_pos = b.min_pos;
else if (res.min_val != b.min_val) res.min_pos = a.min_pos;
else res.min_pos = min(a.min_pos, b.min_pos);
// unite here
return res;
}
inline void push(int x, int l, int r) {
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
// lazy here
if (tree[x].ad != 0) {
tree[x + 1].apply(l, y, tree[x].ad);
tree[z].apply(y + 1, r, tree[x].ad);
}
}
inline void pull(int x, int z) {
tree[x] = unite(tree[x + 1], tree[z]);
}
int n;
vector<node> tree;
void build(int x, int l, int r) {
if (l == r) {
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
build(x + 1, l, y);
build(z, y + 1, r);
pull(x, z);
}
template <typename M, typename... T>
void build(int x, int l, int r, const vector<M> &v, const T&... t) {
if (l == r) {
tree[x].apply(l, r, v[l], t...);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
build(x + 1, l, y, v, t...);
build(z, y + 1, r, v, t...);
pull(x, z);
}
template <typename M, typename... T>
segtree(const vector<M> &v, const T&... t) {
n = v.size();
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1, v, t...);
}
segtree(int _n) : n(_n) {
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1);
}
segtree(){};
node get(int x, int l, int r, int ll, int rr) {
if (ll <= l && r <= rr) {
return tree[x];
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
push(x, l, r);
node res{};
if (rr <= y) {
res = get(x + 1, l, y, ll, rr);
} else {
if (ll > y) {
res = get(z, y + 1, r, ll, rr);
} else {
res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
}
}
pull(x, z);
return res;
}
node get(int ll, int rr) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
return get(0, 0, n - 1, ll, rr);
}
node get(int p) {
assert(0 <= p && p <= n - 1);
return get(0, 0, n - 1, p, p);
}
template <typename... M>
void modify(int x, int l, int r, int ll, int rr, const M&... v) {
// segtree beat condition here
if (ll <= l && r <= rr) {
tree[x].apply(l, r, v...);
return;
}
// A:;
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
push(x, l, r);
if (ll <= y) {
modify(x + 1, l, y, ll, rr, v...);
}
if (rr > y) {
modify(z, y + 1, r, ll, rr, v...);
}
pull(x, z);
}
template <typename... M>
void modify(int ll, int rr, const M&... v) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
modify(0, 0, n - 1, ll, rr, v...);
}
// find_first and find_last call all FALSE elements
// to the left (right) of the sought position exactly once
int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res;
if (f(tree[x + 1])) {
res = find_first_knowingly(x + 1, l, y, f);
} else {
res = find_first_knowingly(z, y + 1, r, f);
}
pull(x, z);
return res;
}
int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
if (!f(tree[x])) {
return -1;
}
return find_first_knowingly(x, l, r, f);
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res = -1;
if (ll <= y) {
res = find_first(x + 1, l, y, ll, rr, f);
}
if (rr > y && res == -1) {
res = find_first(z, y + 1, r, ll, rr, f);
}
pull(x, z);
return res;
}
int find_first(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
return find_first(0, 0, n - 1, ll, rr, f);
}
int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res;
if (f(tree[z])) {
res = find_last_knowingly(z, y + 1, r, f);
} else {
res = find_last_knowingly(x + 1, l, y, f);
}
pull(x, z);
return res;
}
int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
if (!f(tree[x])) {
return -1;
}
return find_last_knowingly(x, l, r, f);
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
int res = -1;
if (rr > y) {
res = find_last(z, y + 1, r, ll, rr, f);
}
if (ll <= y && res == -1) {
res = find_last(x + 1, l, y, ll, rr, f);
}
pull(x, z);
return res;
}
int find_last(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
return find_last(0, 0, n - 1, ll, rr, f);
}
};
/* HOW TO USE
node (Modify here)
info
apply(int l, int r, ...)
// segtree beat condition f
unite(node, node) (Modify here)
push(x, l, r) (Modify here)
pull(x, z)
n, vector<node> tree
build(x, l, r)
segtree(n)
build(x, l, r, vector, state_parameter...)
segtree(vector, state_parameter...)
get(x, l, r, ll, rr) => get(ll, rr) + get(p)
modify(x, l, r, ll, rr, ...) => modify(ll, rr, ...)
// if (f) goto A (Modify here)
if (l <= ll && rr <= r)
//A:; (Modify here)
find_first_knowingly(x, l, r, &f) (not bounded by ll, rr) => find_first(x, l, r, ll, rr, &f) => find_first(ll, rr, &f)
find_last_knowingly(x, l, r, &f) (not bounded by ll, rr) => find_last(x, l, r, ll, rr, &f) => find_last(ll, rr, &f)
*/
const int inf = 1e9;
const int N = 20;
int n;
vector<int> position;
vector<vector<long long>> sL;
vector<vector<long long>> sR;
vector<int> order;
int step;
void init(int k, vector<int> a) {
position.clear();
sL.clear();
sR.clear();
order.clear();
n = a.size();
step = k;
vector<int> A(2 * n);
for (int i = 0; i < 2 * n; i++) A[i] = a[i % n];
segtree st(A);
position.resize(n);
sL.resize(N, vector<long long>(n));
sR.resize(N, vector<long long>(n));
set<int> roots;
auto check = [&](int pos) {
return st.get(pos + n - (k - 1), pos + n - 1).min_val > 0;
};
auto erase = [&](int pos) {
roots.erase(pos);
st.modify(pos + n - (k - 1), pos + n - 1, -1);
if (pos > 0) st.modify(max(0, pos - (k - 1)), pos - 1, -1);
if (pos - (k - 1) < 0) st.modify(pos - (k - 1) + 2 * n, 2 * n - 1, -1);
st.modify(pos, pos, inf);
st.modify(pos + n, pos + n, inf);
auto Lnd = st.get(pos + n - (k - 1), pos + n - 1);
if (Lnd.min_val == 0) {
int p = Lnd.min_pos;
if (p >= n) p -= n;
if (check(p)) {
roots.insert(p);
}
}
auto Rnd = st.get(pos + 1, pos + k - 1);
if (Rnd.min_val == 0) {
int p = Rnd.min_pos;
if (p >= n) p -= n;
if (check(p)) {
roots.insert(p);
}
}
};
for (int i = 0; i < n; i++) if (a[i] == 0 && check(i)) roots.insert(i);
while (roots.size()) {
auto it = roots.begin();
order.push_back(*it);
erase(*it);
}
assert((int) order.size() == n);
for (int i = 0; i < n; i++) position[order[i]] = i;
segtree segs(vector<int>(2 * n, inf));
reverse(order.begin(), order.end());
for (int v : order) {
sL[0][v] = 0;
sR[0][v] = 0;
auto Lnd = segs.get(v + n - (k - 1), v + n);
auto Rnd = segs.get(v, v + (k - 1));
if (Lnd.min_val < inf) {
int p = Lnd.min_pos;
sL[0][v] += v + n - p;
}
if (Rnd.min_val < inf) {
int p = Rnd.min_pos;
sR[0][v] += p - v;
}
segs.modify(v, v, position[v] - inf);
segs.modify(v + n, v + n, position[v] - inf);
}
for (int i = 1; i < N; i++) {
for (int v = 0; v < n; v++) {
int u;
u = (1LL * v - sL[i - 1][v]) % n;
if (u < 0) u += n;
sL[i][v] = sL[i - 1][v] + sL[i - 1][u];
u = (1LL * v + sR[i - 1][v]) % n;
sR[i][v] = sR[i - 1][v] + sR[i - 1][u];
}
}
}
int goR(int x, int y) {
long long len = y - x + (step - 1);
int goal = position[y % n];
for (int b = N - 1; b >= 0; b--) {
long long d = sR[b][x];
int nxt = (d + x) % n;
if (position[nxt] <= goal) {
len -= d;
x = nxt;
}
}
if (len > 2 * (step - 1)) return -1;
return x % n;
}
int goL(int x, int y) {
long long len = x - y + (step - 1);
int goal = position[(y + n) % n];
for (int b = N - 1; b >= 0; b--) {
long long d = sL[b][x];
int nxt = (-d + x) % n;
if (nxt < 0) nxt += n;
if (position[nxt] <= goal) {
len -= d;
x = nxt;
}
}
if (len > 2 * (step - 1)) return -1;
return x;
}