#include "werewolf.h"
#include <bits/stdc++.h>
#define MAX 200001
#define pb push_back
using namespace std;
vector<int> f(vector<int> &a,vector<int> &b){
int i,j;
i=j=0;
vector<int> res;
while(i<(int)a.size() && j<(int)b.size()){
if(a[i]<b[j]){
res.pb(a[i]);
i++;
}
else{
res.pb(b[j]);
j++;
}
}
while(i<(int)a.size()){
res.pb(a[i]);
i++;
}
while(j<(int)b.size()){
res.pb(b[j]);
j++;
}
return res;
}
struct segtree{
int size;
vector<vector<int>> tree;
void init(int n){
size=1;
while(size<n){
size*=2;
}
tree.resize(2*size);
}
void build(vector<int> &a,int x,int lx,int rx){
if(rx-lx==1){
if(lx<(int)a.size()){
tree[x]={a[lx]};
}
return;
}
int m=(lx+rx)/2;
build(a,2*x+1,lx,m);
build(a,2*x+2,m,rx);
tree[x]=f(tree[2*x+1],tree[2*x+2]);
}
void build(vector<int> &a){
build(a,0,0,size);
}
bool get_res(int l,int r,int x,int lx,int rx,int l1,int r1){
if(lx>=r || rx<=l){
return false;
}
if(lx>=l && rx<=r){
auto it=lower_bound(tree[x].begin(),tree[x].end(),l1);
if(it==tree[x].end() || *it>r1){
return false;
}
return true;
}
int m=(lx+rx)/2;
bool s1,s2;
s1=get_res(l,r,2*x+1,lx,m,l1,r1);
s2=get_res(l,r,2*x+2,m,rx,l1,r1);
s1|=s2;
return s1;
}
bool get_res(int l,int r,int l1,int r1){
return get_res(l,r,0,0,size,l1,r1);
}
};
struct DSU{
vector<int> e,mx,mn;
void init(int n){
e.resize(n,-1);
mx.resize(n);
mn.resize(n);
for(int i=0;i<n;i++){
mn[i]=i;
mx[i]=i;
}
}
int get(int x){
if(e[x]<0){
return x;
}
return e[x]=get(e[x]);
}
int get_mn(int x){
return mn[get(x)];
}
int get_mx(int x){
return mx[get(x)];
}
bool unite(int x,int y){
x=get(x);
y=get(y);
if(x==y) return false;
if(e[x]<e[y]){
swap(x,y);
}
e[y]+=e[x];
mx[y]=max(mx[y],mx[x]);
mn[y]=min(mn[y],mn[x]);
e[x]=y;
return true;
}
};
int bl1[MAX][20],bl2[MAX][20],in1[MAX],in2[MAX],out1[MAX],out2[MAX];
int tim=-1;
vector<vector<int>> g,g1,g2;
void dfs1(int v){
in1[v]=++tim;
for(auto x:g1[v]){
if(in1[x]!=-1){
continue;
}
dfs1(x);
}
out1[v]=tim;
}
void dfs2(int v){
in2[v]=++tim;
for(auto x:g2[v]){
if(in2[x]!=-1){
continue;
}
dfs2(x);
}
out2[v]=tim;
}
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 = S.size();
int M = X.size();
g.clear();
g.resize(N);
g1.clear();
g1.resize(N);
g2.clear();
g2.resize(N);
vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
A[i] = 0;
}
DSU dsu1,dsu2;
dsu1.init(N);
dsu2.init(N);
for(int i=0;i<M;i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for(int i=0;i<N;i++){
bl1[i][0]=bl2[i][0]=in1[i]=in2[i]=-1;
}
for(int i=0;i<N;i++){
for(auto x:g[i]){
int h=dsu1.get_mx(x);
if(x<i && dsu1.unite(i,x)){
g1[i].push_back(h);
g1[h].push_back(i);
bl1[h][0]=i;
}
}
}
for(int i=N-1;i>=0;i--){
for(auto x:g[i]){
int h=dsu2.get_mn(x);
if(x>i && dsu2.unite(i,x)){
g2[i].push_back(h);
g2[h].push_back(i);
bl2[h][0]=i;
}
}
}
for(int i=1;i<20;i++){
for(int j=0;j<N;j++){
if(bl1[j][i-1]==-1){
bl1[j][i]=-1;
}
else{
bl1[j][i]=bl1[bl1[j][i-1]][i-1];
}
if(bl2[j][i-1]==-1){
bl2[j][i]=-1;
}
else{
bl2[j][i]=bl2[bl2[j][i-1]][i-1];
}
}
}
tim=-1;
for(int i=N-1;i>=0;i--){
if(in1[i]!=-1){
continue;
}
dfs1(i);
}
tim=-1;
for(int i=0;i<N;i++){
if(in2[i]!=-1){
continue;
}
dfs2(i);
}
vector<int> a(N);
for(int i=0;i<N;i++){
a[in1[i]]=in2[i];
}
segtree st;
st.init(N);
st.build(a);
for(int i=0;i<Q;i++){
for(int j=19;j>=0;j--){
if(bl1[E[i]][j]!=-1 && bl1[E[i]][j]<=R[i]){
E[i]=bl1[E[i]][j];
}
}
for(int j=19;j>=0;j--){
if(bl2[S[i]][j]!=-1 && bl2[S[i]][j]>=L[i]){
S[i]=bl2[S[i]][j];
}
}
A[i]=st.get_res(in1[E[i]],out1[E[i]],in2[S[i]],out2[S[i]]);
}
return A;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
494 ms |
128640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
