#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "werewolf.h"
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define F first
#define S second
using namespace std;
using pii = pair<int, int>;
const int MAXN = 200000;
struct DSU {
int p[MAXN + 10];
int rk[MAXN + 10];
vector<int> adj[MAXN + 10];
int l[MAXN + 10], r[MAXN + 10];
int cur_id;
void init(int n) {
cur_id = 0;
For(i, 0, n - 1) {
adj[i].clear();
l[i] = r[i] = i;
p[i] = -1;
rk[i] = 1;
}
}
int find(int n) {
if(p[n] < 0) return n;
return find(p[n]);
}
void uni(int a, int b) {
a = find(a); b = find(b);
if(a == b) return;
if(rk[a] < rk[b]) swap(a, b);
p[b] = a;
adj[a].eb(b);
rk[a] += rk[b];
r[a] = r[b];
}
void dfs(int n, int *id) {
id[n] = cur_id;
cur_id++;
for(auto &i:adj[n]) {
dfs(i, id);
}
}
void build_tree(int n, int *id) {
For(i, 0, n - 1) if(p[i] < 0) {
dfs(i, id);
}
}
void out(int n) {
cerr << "Tree:\n";
For(i, 0, n - 1) cerr << p[i] << " \n"[i == n - 1];
For(i, 0, n - 1) cerr << l[i] << " \n"[i == n - 1];
For(i, 0, n - 1) cerr << r[i] << " \n"[i == n - 1];
}
} dsu;
#define LO(x) ((x) & (-(x)))
struct BIT {
int n;
int a[MAXN + 10];
void init(int _n) {
n = _n;
memset(a, 0, sizeof(a));
}
void add(int i, int x) {
i++;
while(i <= n) {
a[i] += x;
i += LO(i);
}
}
int ask(int i) {
i++;
int res = 0;
while(i) {
res += a[i];
i -= LO(i);
}
return res;
}
int ask(int l, int r) {
return ask(r - ask(l - 1));
}
} bit;
struct Query {
int s, e, l, r;
int sl, sr, el, er;
int ans;
};
struct SwpEvent {
Query* qry;
bool add; // true for +, false for -
int x;
};
vector<int> adj[MAXN + 10];
int px[MAXN + 10];
int py[MAXN + 10];
Query queries[MAXN + 10];
// stage 1: build trees & find ranges
void owo1(int n, int q) {
vector<Query*> qrys(q);
For(i, 0, q - 1) {
qrys[i] = queries + i;
}
int ptr;
sort(all(qrys), [&](Query* const &p1, Query* const &p2) {
return p1->l > p2->l;
});
ptr = 0;
dsu.init(n);
Forr(i, n - 1, 0) {
for(auto &j:adj[i]) if(j > i) {
dsu.uni(i, j);
}
while(ptr < q && qrys[ptr]->l == i) {
auto &qry = *qrys[ptr];
int rt = dsu.find(qry.s);
qry.sl = dsu.l[rt];
qry.sr = dsu.r[rt];
ptr++;
}
}
dsu.build_tree(n, px);
For(i, 0, q - 1) {
auto &qry = queries[i];
qry.sl = px[qry.sl];
qry.sr = px[qry.sr];
}
// dsu.out(n);
sort(all(qrys), [&](Query* const &p1, Query* const &p2) {
return p1->r < p2->r;
});
ptr = 0;
dsu.init(n);
For(i, 0, n - 1) {
for(auto &j:adj[i]) if(j < i) {
dsu.uni(i, j);
}
while(ptr < q && qrys[ptr]->r == i) {
auto &qry = *qrys[ptr];
int rt = dsu.find(qry.e);
qry.el = dsu.l[rt];
qry.er = dsu.r[rt];
ptr++;
}
}
dsu.build_tree(n, py);
For(i, 0, q - 1) {
auto &qry = queries[i];
qry.el = py[qry.el];
qry.er = py[qry.er];
}
// dsu.out(n);
// For(i, 0, q - 1) {
// auto &qry = queries[i];
// cerr << qry.sl << "," << qry.sr << " " << qry.el << "," << qry.er << "\n";
// }
}
// stage 2: do sweeping line
void owo2(int n, int q) {
vector<SwpEvent> ev;
For(i, 0, q - 1) {
ev.push_back((SwpEvent){ queries + i, 0, queries[i].sl - 1 });
ev.push_back((SwpEvent){ queries + i, 1, queries[i].sr });
}
sort(all(ev), [&](const SwpEvent &a, const SwpEvent &b) {
return a.x < b.x;
});
int ptr = 0;
while(ptr < sz(ev) && ev[ptr].x < 0) {
ptr++;
}
vector<int> y(n, -1);
For(i, 0, n - 1) {
y[px[i]] = py[i];
// cerr << px[i] << " " << py[i] << "\n";
}
bit.init(n);
For(x, 0, n - 1) {
bit.add(y[x], 1);
while(ptr < sz(ev) && ev[ptr].x == x) {
Query *qry = ev[ptr].qry;
int res = bit.ask(qry->el, qry->er);
if(ev[ptr].add) qry->ans += res;
else qry->ans -= res;
ptr++;
}
}
}
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 = sz(S);
For(i, 0, sz(X) - 1) {
int a = X[i], b = Y[i];
adj[a].eb(b);
adj[b].eb(a);
}
For(i, 0, Q - 1) {
auto &qry = queries[i];
qry.s = S[i];
qry.e = E[i];
qry.l = L[i];
qry.r = R[i];
}
owo1(N, Q);
owo2(N, Q);
vector<int> ans;
For(i, 0, Q - 1) {
ans.eb(queries[i].ans != 0);
}
return ans;
// int Q = S.size();
// vector<int> A(Q);
// for (int i = 0; i < Q; ++i) {
// A[i] = 0;
// }
// return A;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
10452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
10452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
316 ms |
59676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
10452 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
