#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 2e5 + 2;
const int lg = 20;
vector <int> ad [maxn];
vector <int> reach [2][maxn * 2];
int dsu [maxn * 2];
int bit [maxn * 2 + 200];
int up [2][maxn * 2][lg];
int in [2][maxn * 2];
int val [2][maxn * 2];
int sz [2][maxn * 2];
int ps = 5;
int dad (int x) {
return dsu[x] = (x == dsu[x] ? x: dad(dsu[x]));
}
void dfs (int t, int u) {
in[t][u] = ++ps, sz[t][u] = 1;
for (int v: reach[t][u]) {
up[t][v][0] = u;
for (int i = 1; i < lg; i++){
up[t][v][i] = up[t][up[t][v][i-1]][i-1];
}
dfs(t, v);
sz[t][u]+=sz[t][v];
}
}
void add (int x, int y) {
for (; x < maxn * 2 + 20; x+=x & -x) bit[x]+=y;
}
int query (int x) {
int rs = 0;
for (; x; x-=x & -x) rs+=bit[x];
return rs;
}
struct event {
int type; // 1 -> start, 2 -> point, 3 -> end
int x; // OX
int l; // OY
int r; // OY
int idx;
inline bool operator < (const event& oth) const {
if (x == oth.x) return type < oth.type;
return x < oth.x;
}
};
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 M = X.size(), Q = L.size();
vector <int> rs (Q);
for (int i = 0; i < M; i++){
ad[X[i]].push_back(Y[i]);
ad[Y[i]].push_back(X[i]);
}
iota (dsu, dsu + 2 * maxn, 0);
int ct0 = N - 1, ct1 = N - 1;
for (int i = 0; i < N; i++){
for (int j: ad[i]) {
if (j > i) continue;
int p1 = dad(j), p2 = dad(i);
if (p1 != p2) {
ct0++;
reach[0][ct0].push_back(p1);
reach[0][ct0].push_back(p2);
val[0][ct0] = i;
dsu[p1] = dsu[p2] = ct0;
}
}
}
iota (dsu, dsu + 2 * maxn, 0);
for (int i = N - 1; i >= 0; i--) {
for (int j: ad[i]) {
if (j < i) continue;
int p1 = dad(j), p2 = dad(i);
if (p1 != p2) {
ct1++;
reach[1][ct1].push_back(p1);
reach[1][ct1].push_back(p2);
val[1][ct1] = i;
dsu[p1] = dsu[p2] = ct1;
}
}
}
dfs(0, ct0);
dfs(1, ct1);
val[1][0] = -1e9;
val[0][0] = 1e9;
for (int i = 0; i < Q; i++){
for (int j = lg - 1; j >= 0; j--){
if (val[1][up[1][S[i]][j]] >= L[i]) S[i] = up[1][S[i]][j];
if (val[0][up[0][E[i]][j]] <= R[i]) E[i] = up[0][E[i]][j];
}
}
vector <event> ev;
for (int i = 0; i < N; i++){
ev.push_back({2, in[1][i], in[0][i], in[0][i], i});
}
for (int i = 0; i < Q; i++){
ev.push_back({1, in[1][S[i]], in[0][E[i]], in[0][E[i]] + sz[0][E[i]] - 1, i});
ev.push_back({3, in[1][S[i]] + sz[1][S[i]] - 1, in[0][E[i]], in[0][E[i]] + sz[0][E[i]] - 1, i});
}
sort(ev.begin(), ev.end());
for (auto& [t, x, l, r, id]: ev) {
if (t == 1) {
rs[id] -= query(r) - query(l - 1);
}
else if (t == 2) {
add(l, 1);
}
else {
rs[id] += query(r) - query(l - 1);
}
}
for (int i = 0; i < Q; i++){
rs[i] = !!rs[i];
}
return rs;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
25428 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
25456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
25428 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
25456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
736 ms |
149532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
25428 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
25456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
