#define pii pair<int, int>
#define INF numeric_limits<int>::max()/2
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
void dfsSub1(int l, int r, vector<vector<int>>& adjlist, int i, vector<bool>& visited)
{
visited[i] = true;
for(int j : adjlist[i])
{
if(!visited[j] && l <= j && j <= r)
{
dfsSub1(l, r, adjlist, j, visited);
}
}
}
int left(int i)
{
return 2*i;
}
int right(int i)
{
return 2*i+1;
}
pii query(int i, vector<pii>& s, int a, int b, int l, int r)
{
if(l <= a && b <= r)
{
return s[i];
}
if(r < a || b < l)
{
return {INF, 0};
}
int mid = (a+b)/2;
pii one = query(left(i), s, a, mid, l, r);
pii two = query(right(i), s, mid+1, b, l, r);
pii res;
res.first = min(one.first, two.first);
res.second = max(one.second, two.second);
return res;
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R)
{
int n = N;
vector<vector<int>> adjlist(n, vector<int> (0));
for(int i = 0; i < (int) X.size(); i++)
{
int a = X[i];
int b = Y[i];
adjlist[a].push_back(b);
adjlist[b].push_back(a);
}
if(N <= 3000 && (int) X.size() <= 6000 && (int) S.size() <= 3000)
{
vector<int> output(S.size());
for(int t = 0; t < (int) S.size(); t++)
{
int l = L[t];
int r = R[t];
int s = S[t];
int e = E[t];
vector<bool> visited(n, false);
dfsSub1(l, numeric_limits<int>::max()/2, adjlist, s, visited);
for(int i = 0; i < n; i++)
{
if(visited[i] && l <= i && i <= r)
{
dfsSub1(0, r, adjlist, i, visited);
}
}
output[t] = visited[e];
}
return output;
}
//Now, we have a line
vector<int> pos(n); //Index on line
vector<int> line(n); //Index of line position in node array
int start = 0;
while(adjlist[start].size() == 2)
{
start++;
}
int counter = 0;
vector<bool> visited(n, false);
while(true)
{
pos[start] = counter;
line[counter] = start;
visited[start] = true;
if(adjlist[start].size() == 1 && counter != 0)
{
break;
}
counter++;
if(visited[adjlist[start][0]])
{
start = adjlist[start][1];
}
else
{
start = adjlist[start][0];
}
}
//build segtree:
int segnodes = 1;
while(2*n > segnodes)
{
segnodes *= 2;
}
vector<pii> s(segnodes, {INF, 0}); //min, max
for(int i = 0; i < n; i++)
{
s[i+segnodes/2] = {line[i], line[i]};
}
for(int i = segnodes/2-1; i > 0; i--)
{
s[i].first = min(s[left(i)].first, s[right(i)].first);
s[i].second = max(s[left(i)].second, s[right(i)].second);
}
//Answer queries:
vector<int> res(S.size());
for(int t = 0; t < (int) S.size(); t++)
{
int l = L[t];
int r = R[t];
int start = S[t];
int e = E[t];
start = pos[start]+1;
e = pos[e]+1;
if(start < e)
{
//Going to the right
//How far can the human go?
int left = start;
int right = n;
while(left < right)
{
int mid = (left+right+1)/2;
if(query(1, s, 1, segnodes/2, start, mid).first >= l)
{
left = mid;
}
else
{
right = mid-1;
}
}
int human = left;
//How far can the wolf go?
left = 1;
right = e;
while(left < right)
{
int mid = (left+right)/2;
if(query(1, s, 1, segnodes/2, mid, e).second <= r)
{
right = mid;
}
else
{
left = mid+1;
}
}
int wolf = left;
//Result:
if(human >= wolf)
{
res[t] = 1;
}
else
{
res[t] = 0;
}
}
else
{
//Going to the left
//How far can the human go?
int left = 1;
int right = start;
while(left < right)
{
int mid = (left+right)/2;
if(query(1, s, 1, segnodes/2, mid, start).first >= l)
{
right = mid;
}
else
{
left = mid+1;
}
}
int human = left;
//How far can the wolf go?
left = e;
right = n;
while(left < right)
{
int mid = (left+right+1)/2;
if(query(1, s, 1, segnodes/2, e, mid).second <= r)
{
left = mid;
}
else
{
right = mid-1;
}
}
int wolf = left;
//Result:
if(human <= wolf)
{
res[t] = 1;
}
else
{
res[t] = 0;
}
}
}
return res;
}
