#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using vi = vector<int>;
const ll inf = 1e9;
#define all(v) v.begin(), v.end()
#define sz(v) ((int)v.size())
#define pb push_back
#define endl '\n'
#define fst first
#define scn second
const int N = 2e5;
const int K = 22;
vi adj[N];
struct dsu{
int s[N];
int in[N];
vector<vi> p;
vector<vi> dch;
int n;
dsu(int _n) {
n = _n;
p.resize(n);
dch.resize(n);
for (int i = 0; i < n; ++i) {
p[i].assign(K,0);
p[i][0] = i;
p[i][1] = i;
s[i] = 1;
}
}
int
getp(int x)
{
return p[x][1] = (x == p[x][1]) ? x : getp(p[x][1]) ;
}
void
conc(int a, int b)
{
a = getp(a);
b = getp(b);
if (a == b) return;
if (a < b) swap(a,b);
dch[a].pb(b);
p[b][0] = a;
p[b][1] = a;
s[a] += s[b];
return;
}
int
dfs(int x, int cnt)
{
in[x] = cnt++;
for(int u : dch[x])
cnt = dfs(u, cnt);
return cnt;
}
void
gen()
{
dfs(n-1,0);
for (int j = 1; j < K; ++j) {
for (int i = 0; i < n; ++i) {
p[i][j] = p[p[i][j-1]][j-1];
}
}
return;
}
void
query(int& x1, int& x2, int st, int v)
{
++v;
for (int j = K-1; j >= 0; --j) {
if (p[st][j] < v) st = p[st][j];
}
x1 = in[st];
x2 = x1 + s[st]-1;
return;
}
};
struct aib{
vi tr;
int n;
aib(int _n) {
n = _n;
tr.assign(n,0);
}
void
add(int x, int v)
{
for(; x < n; x |= (x+1))
tr[x] += v;
return;
}
int
query(int x)
{
int res = 0;
for (; x >= 0; x = (x&(x+1))-1)
res += tr[x];
return res;
}
int
query(int l, int r)
{
return query(r) - query(l-1);
}
};
vector<int>
check_validity(int n, vector<int> x, vector<int> y,
vector<int> b, vector<int> e, vector<int> l, vector<int> r) {
for (int i = 0; i < sz(x); ++i) {
adj[x[i]].pb(y[i]);
adj[y[i]].pb(x[i]);
}
dsu up(n), dn(n);
for (int i = 0; i < n; ++i) {
for (int u : adj[i])
if (u < i) up.conc(i, u);
}
for (int i = n-1; i >= 0; --i) {
for (int u : adj[i])
if (u > i) dn.conc(n-1-i, n-1-u);
}
up.gen();
dn.gen();
int q = sz(l);
vi ans(q,0);
vector<pair<int,int>> in, out;
sort(in.begin(), in.end());
sort(out.begin(), out.end());
vi y1(q),y2(q);
for (int i = 0; i < q; ++i) {
int x1, x2, x3, x4;
up.query(x1,x2, e[i], r[i]);
dn.query(x3,x4, n-1-b[i], n-1-l[i]);
in.pb({x1,i});
out.pb({x2,i});
y1[i] = x3;
y2[i] = x4;
}
vi pos(n);
for (int i = 0; i < n; ++i) pos[up.in[i]] = n-i-1;
int pi, po;
pi = po = 0;
aib tr(n);
for (int i = 0; i < n; ++i) {
while(pi < sz(in)) {
if (i < in[pi].fst) break;
ans[in[pi].scn] -= tr.query(y1[in[pi].scn], y2[in[pi].scn]);
++pi;
}
tr.add(dn.in[pos[i]],1);
while(po < sz(out)) {
if (i < out[po].fst) break;
ans[out[po].scn] += tr.query(y1[out[po].scn], y2[out[po].scn]);
++po;
}
}
for (int i = 0; i < q; ++i)
if (ans[i]) ans[i] = 1;
return ans;
}
#ifdef ONPC
void
solve()
{
int n, m, q;
cin >> n >> m >> q;
vector<int> x(m), y(m), s(q), e(q), l(q), r(q);
for (int i = 0; i < m; ++i) cin >> x[i];
for (int i = 0; i < m; ++i) cin >> y[i];
for (int i = 0; i < q; ++i) cin >> s[i];
for (int i = 0; i < q; ++i) cin >> e[i];
for (int i = 0; i < q; ++i) cin >> l[i];
for (int i = 0; i < q; ++i) cin >> r[i];
vector<int> ans = check_validity(n,x,y,s,e,l,r);
for (int a : ans) {
cout << a << ' ';
}
cout << endl;
}
int32_t
main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
freopen("in", "r", stdin);
int t = 1;
/* cin >> t; */
while(t--)
solve();
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
726 ms |
95532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
