#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int oo = 1e9;
int n, q, cal[N], ans[N];
vector<int> p[N];
struct tree{
int pa[N], sz[N], Min[N], Max[N], in[N], en[N], demin, be[N], f[N][22];
vector<int> g[N];
void pre(){
for(int i = 1; i <= n; i ++) pa[i] = i, sz[i] = 1, Max[i] = Min[i] = i;
}
int fin(int u){
return pa[u] == u ? u : pa[u] = fin(pa[u]);
}
bool dsu(int x,int y){
x = fin(x);
y = fin(y);
if(x == y) return 0;
if(sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
pa[y] = x;
Max[x] = max(Max[x], Max[y]);
Min[x] = min(Min[x], Min[y]);
return 1;
}
void dfs(int u,int v){
in[u] = ++demin;
if(v == 0) for(int i = 0; i <= 18; i ++) f[u][i] = u;
else{
f[u][0] = v;
for(int i = 1; i <= 18; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
}
be[demin] = u;
for(auto j : g[u]){
if(j == v) continue;
dfs(j, u);
}
en[u] = demin;
}
bool kt(int u,int v){
return in[u] <= in[v] && in[v] <= en[u];
}
int Find(int type, int x,int lim){
if(type == 0){
int kq = x;
for(int i = 18; i >= 0; i --) if(f[x][i] <= lim){
kq = f[x][i];
x = f[x][i];
}
return kq;
}else{
int kq = x;
for(int i = 18; i >= 0; i --) if(f[x][i] >= lim){
kq = f[x][i];
x = f[x][i];
}
return kq;
}
}
} T[2];
vector<int> node[N], bit[N];
void fakeup(int x,int y){
for(; x <= n; x += x & -x) node[x].pb(y);
}
void update(int x,int yy){
for(; x <= n; x += x & -x){
for(int y = upper_bound(all(node[x]), yy) - node[x].begin(); y <= node[x].size(); y += y & -y)
bit[x][y]++;
}
}
int get(int x,int yy){
int ret = 0;
for(; x > 0; x -= x & -x){
for(int y = upper_bound(all(node[x]), yy) - node[x].begin(); y > 0; y -= y & -y)
ret += bit[x][y];
}
return ret;
}
int query(int x,int y,int i,int j){
// if(x == 4 && y == 4 && i == 4 && j == 5) cerr << get(y, j) << " " << get(x - 1, j) << " " << get(y, i - 1) << " " << get(x - 1, i - 1) << " fg\n";
return get(y, j) - get(x - 1, j) - get(y, i - 1) + get(x - 1, i - 1);
}
vector<pii> open[N], close[N];
vector<int> check_validity(int _n, vector<int> X,vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
n = _n, q = L.size();
for(int i = 0; i < X.size(); i ++){
int x = ++X[i], y = ++Y[i];
p[x].pb(y);
p[y].pb(x);
// cerr << x << " " << y << " k\n";
}
T[0].pre(), T[1].pre();
for(int i = 1; i <= n; i ++) for(auto j : p[i]) if(j < i){
int tmp = T[0].Max[T[0].fin(j)];
if(T[0].dsu(i, j)){
T[0].g[i].pb(tmp);
// cerr << i << " " << tmp << " inc\n";
}
}
// cerr << " ggg\n";
T[0].dfs(n, 0);
for(int i = n; i >= 1; i --) for(auto j : p[i]) if(j > i){
int tmp = T[1].Min[T[1].fin(j)];
if(T[1].dsu(i, j)){
T[1].g[i].pb(tmp);
// cerr << i << " " << tmp << "dec\n";
}
}
T[1].dfs(1, 0);
// for(int i = 1; i <= n; i ++) cerr << i << " " << T[0].in[i] << " " << T[0].en[i]<< " " << T[1].in[i] << " " << T[1].en[i] << " j\n";
for(int i = 0; i < q; i ++){
int s = ++S[i], e = ++E[i], l = ++L[i], r = ++R[i];
if(e > R[i] || s < l){
ans[i] = 0;
continue;
}
int ce = T[0].Find(0, e, r), cs = T[1].Find(1, s, l);
// cerr << s << " " << e << " " << l << " " << r << " " << cs << " " << ce << " " << T[1].in[cs] << " " << T[1].en[cs] << " " << L[i] << " " << R[i] << " t\n";
open[T[0].in[ce] - 1].pb({i, cs});
close[T[0].en[ce]].pb({i, cs});
fakeup(T[1].in[cs] - 1, l - 1);
fakeup(T[1].in[cs] - 1, r);
fakeup(T[1].en[cs], l - 1);
fakeup(T[1].en[cs], r);
}
for(int i = 1; i <= n; i ++){
fakeup(T[1].in[i], i);
// cerr << T[1].in[i] << " " << i << " uu\n";
}
for(int i = 1; i <= n; i ++){
sort(all(node[i]));
node[i].resize(unique(all(node[i])) - node[i].begin());
bit[i].pb(0);
for(auto j : node[i]) bit[i].pb(0);
}
for(int i = 1; i <= n; i ++){
int u = T[0].be[i];
update(T[1].in[u], u);
// cerr << T[1].in[u] << " " << u << " y\n";
// cerr << query(4, 4, 4, 5) << " hghg\n";
for(auto [id, j] : open[i]){
int tmp = query(T[1].in[j], T[1].en[j], L[id], R[id]);;
// cerr << id << " " << j << " " << tmp << " d\n";
cal[id] -= query(T[1].in[j], T[1].en[j], L[id], R[id]);
}
for(auto [id, j] : close[i]){
int tmp = query(T[1].in[j], T[1].en[j], L[id], R[id]);
// cerr << id << " " << j << " " << tmp << " " << T[1].in[j] << " " << T[1].en[j] << " " << L[id] << " " << R[id] << " i\n";
cal[id] += query(T[1].in[j], T[1].en[j], L[id], R[id]);
}
}
vector<int> out;
for(int i = 0; i < q; i ++){
// cerr << cal[i] << " ";
if(!cal[i]) out.pb(0);
else out.pb(1);
}
// cerr << "h\n";
return out;
}
//#define lpv
#ifdef lpv
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")){
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
vector<int> x, y, st, ed, lf, rt;
int n, m, q; cin >> n >> m >> q;
for(int i = 1; i <= m; i ++){
int gg, hh; cin >> gg >> hh;
x.pb(gg),y.pb(hh);
}
for(int i = 1; i <= q; i ++){
int g, h, j, k; cin >> g >> h >> j >> k;
st.pb(g), ed.pb(h), lf.pb(j), rt.pb(k);
}
vector<int> oo = check_validity(n,x,y,st,ed,lf,rt);
for(auto j : oo) cout << j << " ";
}
#endif // lpv
Compilation message
werewolf.cpp: In function 'void update(int, int)':
werewolf.cpp:83:72: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(int y = upper_bound(all(node[x]), yy) - node[x].begin(); y <= node[x].size(); y += y & -y)
| ~~^~~~~~~~~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int i = 0; i < X.size(); i ++){
| ~~^~~~~~~~~~
werewolf.cpp:154:18: warning: unused variable 'j' [-Wunused-variable]
154 | for(auto j : node[i]) bit[i].pb(0);
| ^
werewolf.cpp:162:17: warning: unused variable 'tmp' [-Wunused-variable]
162 | int tmp = query(T[1].in[j], T[1].en[j], L[id], R[id]);;
| ^~~
werewolf.cpp:167:17: warning: unused variable 'tmp' [-Wunused-variable]
167 | int tmp = query(T[1].in[j], T[1].en[j], L[id], R[id]);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
486 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
486 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
805 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
486 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
