| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 434722 | yuto1115 | 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 "plants.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;
template<class T>
bool chmin(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
// min, arg_min
using S = pair<int, int>;
const S e = {inf, -1};
S op(const S &l, const S &r) {
return (l.first <= r.first ? l : r);
}
using F = int;
const F id = 0;
F composition(const F &g, const F &f) {
return g + f;
}
S mapping(const F &f, const S &x) {
return S(x.first + f, x.second);
}
class lazy_segtree {
int log, n;
vector<S> d;
vector<F> lazy;
void update(int i) {
assert(i < n);
d[i] = op(d[2 * i], d[2 * i + 1]);
}
void all_apply(int i, const F &f) {
d[i] = mapping(f, d[i]);
if (i < n) lazy[i] = composition(f, lazy[i]);
}
void propagate(int i) {
assert(i < n);
all_apply(2 * i, lazy[i]);
all_apply(2 * i + 1, lazy[i]);
lazy[i] = id;
}
public:
lazy_segtree(const vector<S> &init) {
log = 0;
while ((1 << log) < init.size()) log++;
n = 1 << log;
d.assign(2 * n, e);
rep(i, init.size()) d[n + i] = init[i];
rrep(i, n) update(i);
lazy.assign(n, id);
}
S prod(int l, int r) {
assert(0 <= l and l <= r and r <= n);
l += n, r += n;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) propagate(l >> i);
if (((r >> i) << i) != r) propagate(r >> i);
}
S fl = e, fr = e;
while (l < r) {
if (l & 1) fl = op(fl, d[l++]);
if (r & 1) fr = op(d[--r], fr);
l >>= 1, r >>= 1;
}
return op(fl, fr);
}
void apply(int l, int r, const F &f) {
assert(0 <= l and l <= r and r <= n);
l += n, r += n;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) propagate(l >> i);
if (((r >> i) << i) != r) propagate(r >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1, r >>= 1;
}
l = l2, r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update(r >> i);
}
}
};
int k, n;
vi p;
vvi v;
vi to, rev;
void init(int _k, vi r) {
k = _k;
n = r.size();
vector<S> init(n);
rep(i, n) init[i] = {r[i], i};
lazy_segtree st(init);
set<int> can;
auto get_min = [&](int i, int w) {
if (i >= w) return st.prod(i - w, i);
int rem = w - i;
return op(st.prod(n - rem, n), st.prod(0, i));
};
auto dec = [&](int i) {
if (i >= k - 1) {
st.apply(i - k + 1, i, -1);
return;
}
int rem = k - 1 - i;
st.apply(n - rem, n, -1);
st.apply(0, i, -1);
};
auto check = [&](int i) {
S s = get_min(i, k - 1);
if (s.first > 0) can.insert(i);
};
auto erase = [&](int i) {
st.apply(i, i + 1, inf);
dec(i);
S s = get_min(i, k - 1);
if (s.first == 0) check(s.second);
s = get_min(i, n - 1);
if (s.first == 0) check(s.second);
};
if (n <= 300) {
v.resize(n);
rep(i, n) {
v[i].resize(n);
st = lazy_segtree(init);
can.clear();
rep(j, n) if (!r[j]) check(j);
while (true) {
if (can.count(i)) can.erase(i);
if (can.empty()) break;
int nx = *can.begin();
can.erase(nx);
v[i][nx] = 1;
erase(nx);
}
}
} else {
p.assign(n, -1);
rep(i, n) if (!r[i]) check(i);
rrep(t, n) {
int nx = *can.begin();
can.erase(nx);
p[nx] = t;
erase(nx);
}
to.resize(n);
{
st = lazy_segtree(init);
can.clear();
rep(j, n) if (!r[j]) check(j);
while (true) {
if (can.count(0)) can.erase(0);
if (can.empty()) break;
int nx = *can.begin();
can.erase(nx);
to[nx] = 1;
erase(nx);
}
}
rev.resize(n);
rep(i, n) init[i] = {k - 1 - r[i], i};
{
st = lazy_segtree(init);
can.clear();
rep(j, n) if (!r[j]) check(j);
while (true) {
if (can.count(0)) can.erase(0);
if (can.empty()) break;
int nx = *can.begin();
can.erase(nx);
rev[nx] = 1;
erase(nx);
}
}
}
}
int compare_plants(int x, int y) {
if (n <= 300) {
assert(v[x][y] or v[y][x]);
if (v[x][y] and v[y][x]) return 0;
return (v[x][y] ? -1 : 1);
} else if (x == 0) {
assert(to[y] or rev[y]);
if (to[y] and rev[y]) return 0;
return (to[y] ? -1 : 1);
} else {
return (p[x] > p[y] ? 1 : -1);
}
}
}