#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];
int dsu [maxn];
int bit [maxn * 2 + 200];
int up [2][maxn][lg];
int in [2][maxn];
int val [2][maxn];
int sz [2][maxn];
int ps = 2;
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 i = 1; i < lg; i++){
up[t][u][i] = up[t][up[t][u][i-1]][i-1];
}
for (int v: reach[t][u]) {
up[t][v][0] = u;
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 + maxn, 0);
for (int i = 0; i < N; i++){
for (int j: ad[i]) {
if (j > i) continue;
if (dad(j) != i) {
reach[0][i].push_back(dad(j));
dsu[dad(j)] = i;
}
}
}
iota (dsu, dsu + maxn, 0);
for (int i = N - 1; i >= 0; i--) {
for (int j: ad[i]) {
if (j < i) continue;
if (dad(j) != i) {
reach[1][i].push_back(dad(j));
dsu[dad(j)] = i;
}
}
}
up[0][N-1][0] = N-1;
up[1][0][0] = 0;
dfs(0, N - 1);
ps = 2;
dfs(1, 0);
for (int i = 0; i < Q; i++){
for (int j = lg - 1; j >= 0; j--){
if (up[1][S[i]][j] >= L[i]) S[i] = up[1][S[i]][j];
if (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 |
8 ms |
15316 KB |
Output is correct |
2 |
Correct |
8 ms |
15188 KB |
Output is correct |
3 |
Correct |
7 ms |
15188 KB |
Output is correct |
4 |
Correct |
9 ms |
15188 KB |
Output is correct |
5 |
Correct |
8 ms |
15188 KB |
Output is correct |
6 |
Correct |
9 ms |
15188 KB |
Output is correct |
7 |
Correct |
8 ms |
15296 KB |
Output is correct |
8 |
Correct |
11 ms |
15188 KB |
Output is correct |
9 |
Correct |
9 ms |
15292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15316 KB |
Output is correct |
2 |
Correct |
8 ms |
15188 KB |
Output is correct |
3 |
Correct |
7 ms |
15188 KB |
Output is correct |
4 |
Correct |
9 ms |
15188 KB |
Output is correct |
5 |
Correct |
8 ms |
15188 KB |
Output is correct |
6 |
Correct |
9 ms |
15188 KB |
Output is correct |
7 |
Correct |
8 ms |
15296 KB |
Output is correct |
8 |
Correct |
11 ms |
15188 KB |
Output is correct |
9 |
Correct |
9 ms |
15292 KB |
Output is correct |
10 |
Correct |
14 ms |
16704 KB |
Output is correct |
11 |
Correct |
14 ms |
16696 KB |
Output is correct |
12 |
Correct |
14 ms |
16560 KB |
Output is correct |
13 |
Correct |
14 ms |
16948 KB |
Output is correct |
14 |
Correct |
16 ms |
16940 KB |
Output is correct |
15 |
Correct |
18 ms |
16820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
569 ms |
99012 KB |
Output is correct |
2 |
Correct |
625 ms |
110372 KB |
Output is correct |
3 |
Correct |
556 ms |
105752 KB |
Output is correct |
4 |
Correct |
720 ms |
103928 KB |
Output is correct |
5 |
Correct |
616 ms |
103808 KB |
Output is correct |
6 |
Correct |
635 ms |
103544 KB |
Output is correct |
7 |
Correct |
605 ms |
103440 KB |
Output is correct |
8 |
Correct |
700 ms |
110496 KB |
Output is correct |
9 |
Correct |
658 ms |
105756 KB |
Output is correct |
10 |
Correct |
580 ms |
103952 KB |
Output is correct |
11 |
Correct |
567 ms |
103812 KB |
Output is correct |
12 |
Correct |
668 ms |
103584 KB |
Output is correct |
13 |
Correct |
734 ms |
116984 KB |
Output is correct |
14 |
Correct |
690 ms |
117016 KB |
Output is correct |
15 |
Correct |
637 ms |
117028 KB |
Output is correct |
16 |
Correct |
641 ms |
117124 KB |
Output is correct |
17 |
Correct |
559 ms |
103420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15316 KB |
Output is correct |
2 |
Correct |
8 ms |
15188 KB |
Output is correct |
3 |
Correct |
7 ms |
15188 KB |
Output is correct |
4 |
Correct |
9 ms |
15188 KB |
Output is correct |
5 |
Correct |
8 ms |
15188 KB |
Output is correct |
6 |
Correct |
9 ms |
15188 KB |
Output is correct |
7 |
Correct |
8 ms |
15296 KB |
Output is correct |
8 |
Correct |
11 ms |
15188 KB |
Output is correct |
9 |
Correct |
9 ms |
15292 KB |
Output is correct |
10 |
Correct |
14 ms |
16704 KB |
Output is correct |
11 |
Correct |
14 ms |
16696 KB |
Output is correct |
12 |
Correct |
14 ms |
16560 KB |
Output is correct |
13 |
Correct |
14 ms |
16948 KB |
Output is correct |
14 |
Correct |
16 ms |
16940 KB |
Output is correct |
15 |
Correct |
18 ms |
16820 KB |
Output is correct |
16 |
Correct |
569 ms |
99012 KB |
Output is correct |
17 |
Correct |
625 ms |
110372 KB |
Output is correct |
18 |
Correct |
556 ms |
105752 KB |
Output is correct |
19 |
Correct |
720 ms |
103928 KB |
Output is correct |
20 |
Correct |
616 ms |
103808 KB |
Output is correct |
21 |
Correct |
635 ms |
103544 KB |
Output is correct |
22 |
Correct |
605 ms |
103440 KB |
Output is correct |
23 |
Correct |
700 ms |
110496 KB |
Output is correct |
24 |
Correct |
658 ms |
105756 KB |
Output is correct |
25 |
Correct |
580 ms |
103952 KB |
Output is correct |
26 |
Correct |
567 ms |
103812 KB |
Output is correct |
27 |
Correct |
668 ms |
103584 KB |
Output is correct |
28 |
Correct |
734 ms |
116984 KB |
Output is correct |
29 |
Correct |
690 ms |
117016 KB |
Output is correct |
30 |
Correct |
637 ms |
117028 KB |
Output is correct |
31 |
Correct |
641 ms |
117124 KB |
Output is correct |
32 |
Correct |
559 ms |
103420 KB |
Output is correct |
33 |
Correct |
632 ms |
104776 KB |
Output is correct |
34 |
Correct |
316 ms |
57240 KB |
Output is correct |
35 |
Correct |
711 ms |
109408 KB |
Output is correct |
36 |
Correct |
708 ms |
104676 KB |
Output is correct |
37 |
Correct |
727 ms |
108108 KB |
Output is correct |
38 |
Correct |
655 ms |
105704 KB |
Output is correct |
39 |
Correct |
669 ms |
123632 KB |
Output is correct |
40 |
Correct |
835 ms |
116356 KB |
Output is correct |
41 |
Correct |
526 ms |
107100 KB |
Output is correct |
42 |
Correct |
560 ms |
104760 KB |
Output is correct |
43 |
Correct |
708 ms |
116132 KB |
Output is correct |
44 |
Correct |
710 ms |
108104 KB |
Output is correct |
45 |
Correct |
684 ms |
124020 KB |
Output is correct |
46 |
Correct |
584 ms |
123672 KB |
Output is correct |
47 |
Correct |
641 ms |
117208 KB |
Output is correct |
48 |
Correct |
652 ms |
117028 KB |
Output is correct |
49 |
Correct |
664 ms |
117168 KB |
Output is correct |
50 |
Correct |
613 ms |
117120 KB |
Output is correct |
51 |
Correct |
687 ms |
116388 KB |
Output is correct |
52 |
Correct |
704 ms |
116372 KB |
Output is correct |