#include "werewolf.h"
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
const int maxn=2e5+5;
struct union_find{
int kad[maxn];
int parent[maxn];
int sz[maxn];
union_find(){
for(int i=0; i<maxn; i++){
parent[i]=i;
sz[i]=1;
kad[i]=0;
}
}
int find(int x, int vrij){
if(kad[x]>vrij || parent[x]==x){
return x;
}
return find(parent[x], vrij);
}
void update(int x, int y, int vrij){
x=find(x, vrij);
y=find(y, vrij);
if(sz[x]>sz[y]){
swap(x, y);
}
parent[x]=y;
sz[y]+=sz[x];
kad[x]=vrij;
}
bool query(int x, int y, int vrij){
return find(x, vrij)==find(y, vrij);
}
};
//int pos1[maxn], pos2[maxn];
vector < int > ms[maxn];
vector < int > s, e, l, r;
vector < int > sol;
int n;
/*
bool cmp1(int a, int b){
return l[a]>l[b];
}
bool cmp2(int a, int b){
return r[a]<r[b];
}
*/
union_find U1, U2;
void dodaj1(int x){
for(int i=0; i<(int)ms[x].size(); i++){
if(ms[x][i]<x){
if(!U1.query(x, ms[x][i], x+1)){
U1.update(x, ms[x][i], x+1);
}
}
}
}
void dodaj2(int x){
for(int i=0; i<(int)ms[x].size(); i++){
if(ms[x][i]>x){
if(!U2.query(x, ms[x][i], n-x)){
U2.update(x, ms[x][i], n-x);
}
}
}
}
vector < int > check_validity(int N, vector < int > x, vector < int > y, vector < int > S, vector < int > E, vector < int > L, vector < int > R){
s=S;
e=E;
l=L;
r=R;
n=N;
int m=x.size();
for(int i=0; i<m; i++){
ms[x[i]].push_back(y[i]);
ms[y[i]].push_back(x[i]);
}
int q=s.size();
for(int i=0; i<n; i++){
dodaj1(i);
dodaj2(n-i-1);
}
bool p;
for(int i=0; i<q; i++){
p=1;
for(int j=l[i]; j<=r[i]; j++){
if(U1.query(e[i], j, r[i]+1) && U2.query(s[i], j, n-l[i])){
sol.push_back(1);
p=0;
break;
}
}
if(p){
sol.push_back(0);
}
}
return sol;
}
