#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 50 + 5;
struct Dsu {
int n;
vi loga, par, tim;
vvi dp, tree;
vi l, r;
Dsu() {}
Dsu(int n): n(n) {
par.resize(n);
iota(all(par), 0);
dp.resize(1, vi(n));
tree.resize(n);
tim.resize(n);
}
inline void Add(int t) {
par.push_back(n), dp[0].push_back(n);
tree.push_back({});
tim.push_back(t);
n++;
}
int Find(int i) {
return par[i] == i ? i : par[i] = Find(par[i]);
}
void Union(int a, int b, int t) {
int pa = Find(a), pb = Find(b);
if (pa == pb) return;
dp[0][pa] = dp[0][pb] = n;
par[pa] = par[pb] = n;
Add(t);
tree.back().push_back(pa);
tree.back().push_back(pb);
}
void PreOrder(int node, int &t) {
if (tree[node].empty()) {
l[node] = t++;
r[node] = t;
return;
}
l[node] = n, r[node] = 0;
for (int neighbor : tree[node]) {
PreOrder(neighbor, t);
chkmin(l[node], l[neighbor]), chkmax(r[node], r[neighbor]);
}
}
void Build() {
loga.resize(n + 1);
for (int i = 2; i <= n; i++) loga[i] = loga[i >> 1] + 1;
dp.resize(loga[n] + 1, vi(n));
for (int i = 1; i <= loga[n]; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
}
int t = 0;
l.resize(n), r.resize(n);
PreOrder(n - 1, t);
}
int Jump(int node, int t) {
for (int i = loga[n]; i >= 0; i--) {
if (tim[dp[i][node]] <= t) {
node = dp[i][node];
}
}
return node;
}
};
struct Seg {
vi seg, lp, rp;
Seg() {Add();}
inline void Add() {
seg.push_back(0), lp.push_back(0), rp.push_back(0);
}
int update(int i, int ind, int l = 0, int r = MAX_N) {
int copy = seg.size();
Add();
seg[copy] = seg[ind];
lp[copy] = lp[ind], rp[copy] = rp[ind];
if (l + 1 == r) {
seg[copy] = 1;
return copy;
}
if (i < (l + r) >> 1) {
if (!lp[ind]) {
lp[ind] = seg.size();
Add();
}
int y = update(i, lp[ind], l, (l + r) >> 1);
lp[copy] = y;
} else {
if (!rp[ind]) {
rp[ind] = seg.size();
Add();
}
int y = update(i, rp[ind],(l + r) >> 1, r);
rp[copy] = y;
}
seg[copy]++;
return copy;
}
int query(int a, int b, int ind, int l = 0, int r = MAX_N) {
if (a <= l && r <= b) return seg[ind];
if (r <= a || b <= l) return 0;
return (lp[ind] ? query(a, b, lp[ind], l, (l + r) >> 1) : 0) +
(rp[ind] ? query(a, b, rp[ind], (l + r) >> 1, r) : 0);
}
};
Seg seg = Seg();
int n;
int ind[MAX_N];
int roots[MAX_N];
inline int Sum(int x1, int y1, int x2, int y2) {
int v1 = seg.query(y1, y2, roots[x2]), v2 = seg.query(y1, y2, roots[x1]);
return v1 - v2;
}
vi check_validity(int N, vi X, vi Y, vi s, vi e, vi l, vi r) {
n = N;
int m = X.size();
iota(ind, ind + m, 0);
Dsu d_min(n), d_max(n);
sort(ind, ind + m, [&] (int i, int j) {
return max(X[i], Y[i]) < max(X[j], Y[j]);
});
for (int i = 0; i < m; i++) {
d_min.Union(X[ind[i]], Y[ind[i]], max(X[ind[i]], Y[ind[i]]));
}
sort(ind, ind + m, [&] (int i, int j) {
return min(X[i], Y[i]) > min(X[j], Y[j]);
});
for (int i = 0; i < m; i++) {
d_max.Union(X[ind[i]], Y[ind[i]], n - min(X[ind[i]], Y[ind[i]]));
}
d_min.Build(), d_max.Build();
vii points(n);
for (int i = 0; i < n; i++) {
points[i] = {d_min.l[i], d_max.l[i]};
}
sort(all(points));
for (int i = 0; i < n; i++) {
roots[i + 1] = seg.update(points[i].y, roots[i]);
}
int q = s.size();
vi ans(q);
for (int i = 0; i < q; i++) {
int t_min = r[i], t_max = n - l[i];
int v1 = d_min.Jump(e[i], t_min), v2 = d_max.Jump(s[i], t_max);
int x1 = d_min.l[v1], x2 = d_min.r[v1], y1 = d_max.l[v2], y2 = d_max.r[v2];
ans[i] = Sum(x1, y1, x2, y2) != 0;
}
return ans;
}
//6 6 3
//5 1
//1 2
//1 3
//3 4
//3 0
//5 2
//4 2 1 2
//4 2 2 2
//5 4 3 4
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
161 ms |
27896 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
