#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;
const int maxn = 2e5+5;
struct dsu
{
vector<int> par;
dsu(int n = 0)
{
par.resize(n);
for(int i = 0; i< n; i++) par[i] = i;
}
int findset(int x)
{
if(x == par[x]) return x;
return par[x] = findset(par[x]);
}
};
dsu hum, wolf;
int n, m, q;
vector<int> adj[maxn];
struct tahm
{
int s, e, l, r, id;
int hum, wolf;
tahm(int s, int e, int l, int r, int id): s(s), e(e), l(l), r(r), id(id) {}
};
bool cmpl(tahm a, tahm b)
{
return a.l< b.l;
}
bool cmpr(tahm a, tahm b)
{
return a.r< b.r;
}
vector<tahm> kench;
vector<int> twolf[maxn];
vector<int> thum[maxn];
vector<int> pred;
int numb[maxn];
int lb[maxn];
int rb[maxn];
void dfs(int u = 2*n-2)
{
if(u< n) pred.pb(u);
for(int v : twolf[u]) dfs(v);
}
void calc(int u = 2*n-2)
{
lb[u] = 1e9, rb[u] = -1;
if(u< n) lb[u] = rb[u] = numb[u];
for(int v : twolf[u])
{
calc(v);
lb[u] = min(lb[u], lb[v]);
rb[u] = max(rb[u], rb[v]);
}
// printf("lb[%d] = %d, rb[%d] = %d\n", u, lb[u], u, rb[u]);
}
struct node
{
int val;
node *left, *right;
node(int _val, node* _left, node *_right)
{
val = _val; left = _left; right = _right;
}
node* insert(int x, int L = 0, int R = n-1)
{
if(L<= x && x<= R)
{
if(L == R) return new node(val+1, NULL, NULL);
int M = (L+R)/2;
return new node(val+1, left->insert(x, L, M), right->insert(x, M+1, R));
}
return this;
}
int ask(int i, int j, int L = 0, int R = n-1)
{
if(i> R || j< L) return 0;
if(i<= L && R<= j) return val;
int M = (L+R)/2;
int x = left->ask(i, j, L, M);
int y = right->ask(i, j, M+1, R);
return x+y;
}
};
node* zero = new node(0, NULL, NULL);
node* roots[maxn];
vector<int> elems[maxn];
void comb(int u = 2*n-2)
{
if(u< n)
{
elems[u].pb(numb[u]);
roots[u] = zero->insert(numb[u]);
return;
}
ii big = {0, -1};
for(int v : thum[u])
{
comb(v);
big = max(big, ii((int) elems[v].size(), v));
}
swap(elems[u], elems[big.Y]);
roots[u] = roots[big.Y];
for(int v : thum[u])
{
for(int x : elems[v])
{
roots[u] = roots[u]->insert(x);
}
}
}
vector<int> check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R)
{
n = N;
m = X.size();
q = S.size();
for(int i = 0; i< q; i++) kench.pb(tahm(S[i], E[i], L[i], R[i], i));
for(int i = 0; i< m; i++)
{
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
wolf = dsu(2*n);
sort(kench.begin(), kench.end(), cmpr);
int pt = 0;
int cnt = n;
for(int i = 0; i< n; i++)
{
for(int v : adj[i])
{
if(v< i)
{
int a = wolf.findset(i);
int b = wolf.findset(v);
if(a == b) continue;
wolf.par[a] = wolf.par[b] = cnt;
twolf[cnt].pb(a);
twolf[cnt].pb(b);
// printf("%d-->%d %d-->%d\n", cnt, a, cnt, b);
cnt++;
}
}
while(pt< q && kench[pt].r == i)
{
int e = kench[pt].e;
int pp = wolf.findset(e);
kench[pt].wolf = pp;
pt++;
}
}
// printf("finished wolf\n");
hum = dsu(2*n);
sort(kench.begin(), kench.end(), cmpl);
reverse(kench.begin(), kench.end());
pt = 0;
cnt = n;
for(int i = n-1; i>= 0; i--)
{
for(int v : adj[i])
{
if(v> i)
{
int a = hum.findset(v);
int b = hum.findset(i);
if(a == b) continue;
hum.par[a] = hum.par[b] = cnt;
// printf("%d->%d, %d->%d\n", cnt, a, cnt, b);
thum[cnt].pb(a);
thum[cnt].pb(b);
cnt++;
}
}
while(pt< q && kench[pt].l == i)
{
int s = kench[pt].s;
int pp = hum.findset(s);
kench[pt].hum = pp;
pt++;
}
}
dfs();
// for(int i = 0; i< n; i++) printf("%d ", pred[i]);
// printf("\n");
for(int i = 0; i< n; i++) numb[pred[i]] = i;
calc();
// printf("finished renumbering\n");
zero->left = zero->right = zero;
comb();
vector<int> ans(q);
for(int i = 0; i< q; i++)
{
int wolf = kench[i].wolf, hum = kench[i].hum;
int id = kench[i].id;
int lo = lb[wolf], hi = rb[wolf];
// if(hum == 5) printf("wolf is %d [%d %d] ans is %d\n", wolf, lo, hi, roots[hum]->ask(0, 0));
int res = roots[hum]->ask(lo, hi);
ans[id] = res> 0;
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
19200 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
19200 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
19200 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
19200 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
353 ms |
92016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
19200 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
19200 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
