#include "werewolf.h"
// author : sentheta aka vanwij
#ifdef VANWIJ
#include"/home/user/code/bits/stdc++.h"
#else
#include"bits/stdc++.h"
#endif
using namespace std;
#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second
static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))
#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;
const int N = 2e5+5;
int n, m, q;
V<int> adj[N];
V<int> ans;
// queries details
V<int> qs, qt, ql, qr;
// groups of queries with same l values
V<int> byql[N], byqr[N];
// segments of queries in tree
int qxl[N], qxr[N];
int qyl[N], qyr[N];
// group queries by x-boundaries
V<int> byqxl[N], byqxr[N];
// subtree id of the query
int qroot[N];
// dsu tree
V<int> tadj[2*N];
int tn;
struct Dsu{
int p[2*N];
void reset(){
tn = n;
rep(x,0,2*N){
p[x] = x;
tadj[x].clear();
}
}
int find(int x){
if(p[x]==x) return x;
return p[x] = find(p[x]);
}
bool same(int x,int y){
return find(x)==find(y);
}
void unite(int x,int y){
if((x=find(x))==(y=find(y))) return;
tn++;
assert(tn<2*N);
p[x] = p[y] = tn;
tadj[tn].push_back(x);
tadj[tn].push_back(y);
}
} dsu;
// x-order and y-order of nodes
int ordx[N], ordy[N];
// group nodes by ordx[] values
V<int> byordx[N];
// euler tour
int tin[N], tout[N], tim;
void tdfs(int x){
tin[x] = tim;
if(x<n) tim++;
for(int y : tadj[x]){
tdfs(y);
}
tout[x] = tim-1;
}
// segtree
// point assign update
// range sum query
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
#define mid (tl+tr)/2
struct Segtree{
int sum[2*N];
void upd(int i,int x,int v=0,int tl=0,int tr=n-1){
if(tl==tr){
sum[v] = x; return;
}
if(i<=mid) upd(i,x, lc,tl,mid);
else upd(i,x, rc,mid+1,tr);
sum[v] = sum[lc] + sum[rc];
}
int qry(int l,int r,int v=0,int tl=0,int tr=n-1){
if(r<tl || tr<l) return 0;
if(l<=tl && tr<=r) return sum[v];
return qry(l,r, lc,tl,mid) + qry(l,r, rc,mid+1,tr);
}
} segtree;
V<int> check_validity(int _n,V<int>_u,V<int>_v,
V<int>_s,V<int>_t,V<int>_l,V<int>_r){
n=_n; m=_u.size(); q=_s.size();
qs.swap(_s); qt.swap(_t); ql.swap(_l); qr.swap(_r);
rep(i,0,m){
adj[_u[i]].push_back(_v[i]);
adj[_v[i]].push_back(_u[i]);
}
rep(i,0,q){
byql[ql[i]].push_back(i);
byqr[qr[i]].push_back(i);
}
// bounded right
dsu.reset();
rep(x,0,n){
// make edges with this node
for(int y : adj[x]) if(y<x){
dsu.unite(x,y);
}
// proccess queries
for(int i : byqr[x]){
qroot[i] = dsu.find(qt[i]);
}
}
// euler tour
tim = 0;
tdfs(tn);
assert(tim==n);
rep(x,0,n){
ordx[x] = tin[x];
}
rep(i,0,q){
// get segment
qxl[i] = tin[qroot[i]];
qxr[i] = tout[qroot[i]];
}
// bounded left
dsu.reset();
for(int x=n-1; x>=0; x--){
// make edges with this node
for(int y : adj[x]) if(x<y){
dsu.unite(x,y);
}
// proccess queries
for(int i : byql[x]){
qroot[i] = dsu.find(qs[i]);
}
}
// euler tour
tim = 0;
tdfs(tn);
assert(tim==n);
rep(x,0,n){
ordy[x] = tin[x];
}
rep(i,0,q){
// get segment
qyl[i] = tin[qroot[i]];
qyr[i] = tout[qroot[i]];
}
// sweep check for intersecting segment
ans = V<int>(q);
rep(x,0,n){
assert(0<=ordx[x] && ordx[x]<n);
byordx[0].push_back(0);
// byordx[ordx[x]].push_back(x);
}
assert(0);
rep(i,0,q){
byqxl[qxl[i]].push_back(i);
byqxr[qxr[i]].push_back(i);
}
rep(t,0,n){
// insert points
for(int node : byordx[t]){
segtree.upd(ordy[node], 1);
}
// process queries
// starting query
for(int i : byqxl[t+1]){
ans[i] -= segtree.qry(qyl[i], qyr[i]);
}
// ending query
for(int i : byqxr[t]){
ans[i] += segtree.qry(qyl[i], qyr[i]);
}
}
// convert to boolean
rep(i,0,q) ans[i] = ans[i] > 0;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
79892 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
79892 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
367 ms |
152744 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
79892 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
