| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 277957 | hamerin | Seats (IOI18_seats) | 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 "werewolf.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;
#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed
const i64 PINF = numeric_limits<int>::max();
const i64 NINF = numeric_limits<int>::min();
class disjointSet {
public:
vector<int> p;
disjointSet() = default;
explicit disjointSet(int N) {
p.clear();
p.resize(N);
for (int i = 0; i < N; i++) p[i] = i;
}
int find(int u) { return p[u] = (p[u] == u ? u : find(p[u])); }
void mer(int u, int v) { p[find(v)] = find(u); }
bool sset(int u, int v) { return find(u) == find(v); }
};
namespace Helper {
vector<int> inversePerm(const vector<int> &per) {
int N = per.size();
vector<int> ret(N);
for (int i = 0; i < N; i++) ret[per[i]] = i;
return ret;
}
vector<int> inversePerm(vector<int> &&per) {
int N = per.size();
vector<int> ret(N);
for (int i = 0; i < N; i++) ret[per[i]] = i;
return ret;
}
} // namespace Helper
class tree {
public:
vector<vector<int>> tr, spt;
vector<int> in, out;
int ord;
tree() = default;
explicit tree(int N) {
tr.resize(N), spt.resize(N);
in.resize(N), out.resize(N);
ord = 0;
}
void emplace_edge(int p, int c) {
tr[p].emplace_back(c);
}
void dfs_order(int h) {
in[h] = ++ord;
for (auto t : tr[h]) dfs_order(t);
out[h] = ord;
}
void genSparseTable(int h, int p) {
if (p >= 0) {
int sn = 1;
spt[h].emplace_back(p);
while (true) {
const auto &sppt = spt[spt[h][sn - 1]];
if (sppt.size() < sn) break;
spt[h].emplace_back(sppt[sn - 1]);
++sn;
}
}
for (auto t : tr[h]) genSparseTable(t, h);
}
int find1(int h, int li) {
int p = spt[h].size() - 1;
while (true) {
if (h == li) return h;
if (spt[h][0] > li) return h;
while (spt[h][p] > li) --p;
h = spt[h][p];
p = min(p, (int)spt[h].size() - 1);
}
}
int find2(int h, int li) {
int p = spt[h].size() - 1;
while (true) {
if (h == li) return h;
if (spt[h][0] < li) return h;
while (spt[h][p] < li) --p;
h = spt[h][p];
p = min(p, (int)spt[h].size() - 1);
}
}
};
class segTree {
public:
vector<int> vl;
int N;
segTree() = default;
segTree(int _N) {
vl.resize(1 << 19, NINF);
N = _N;
}
void update(int s, int e, int n, int t, int ne) {
if (s == e) {
vl[n] = ne;
return;
}
int m = (s + e) >> 1;
int k = n << 1;
if (t <= m)
update(s, m, k, t, ne);
else
update(m + 1, e, k + 1, t, ne);
vl[n] = max(vl[k], vl[k + 1]);
}
void update(int t, int ne) { update(1, N, 1, t, ne); }
int query(int s, int e, int n, int l, int r) {
if (r < s || e < l) return NINF;
if (l <= s && e <= r) return vl[n];
int m = (s + e) >> 1;
int k = n << 1;
return max(query(s, m, k, l, r), query(m + 1, e, k + 1, l, r));
}
int query(int l, int r) { return query(1, N, 1, l, r); }
};
using qi = tuple<int, int, int, int>;
using pei = tuple<int, int, int, int, int>;
vector<int> check_validity(int N,
vector<int> X, vector<int> Y,
vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int Q = (int)S.size();
int M = (int)X.size();
vector<vector<int>> graph(N);
for (int i = 0; i < M; i++) {
graph[X[i]].emplace_back(Y[i]);
graph[Y[i]].emplace_back(X[i]);
}
tree tree1(N);
disjointSet dS1(N);
for (int i = 1; i < N; i++) {
set<int> toemplace;
for (auto j : graph[i]) {
if (j < i) toemplace.emplace(dS1.find(j));
}
for (auto j : toemplace) {
dS1.mer(i, j);
tree1.emplace_edge(i, j);
}
}
tree1.dfs_order(N - 1);
tree1.genSparseTable(N - 1, -1);
tree tree2(N);
disjointSet dS2(N);
for (int i = N - 2; i >= 0; i--) {
set<int> toemplace;
for (auto j : graph[i]) {
if (j > i) toemplace.emplace(dS2.find(j));
}
for (auto j : toemplace) {
dS2.mer(i, j);
tree2.emplace_edge(i, j);
}
}
tree2.dfs_order(0);
tree2.genSparseTable(0, -1);
vector<pi> points;
for (int i = 0; i < N; i++) {
points.emplace_back(tree1.in[i], tree2.in[i]);
}
sort(iterall(points));
vector<qi> queries(Q);
for (int i = 0; i < Q; i++) {
queries[i] = {S[i], E[i], L[i], R[i]};
}
vector<pei> rectq; // lx, hx, ly, hy, idx
for (int i = 0; i < Q; i++) {
auto [s, e, l, r] = queries[i];
auto n1 = tree1.find1(e, r);
auto n2 = tree2.find2(s, l);
rectq.emplace_back(tree1.in[n1], tree1.out[n1],
tree2.in[n2], tree2.out[n2], i);
}
sort(iterall(rectq), [](const pei &l, const pei &r) {
return get<1>(l) < get<1>(r);
});
vector<int> ret(Q);
int ptr = 0;
auto sT = segTree(N);
for (auto [lx, hx, ly, hy, idx] : rectq) {
while (ptr < N && points[ptr].first <= hx) {
auto [x, y] = points[ptr];
sT.update(y, x);
++ptr;
}
if (sT.query(ly, hy) >= lx) ret[idx] = 1;
}
return ret;
}