#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int NINF = -555'555'555;
const int INF = 555'555'555;
class segTree{
public:
int lef_index;
int rig_index;
int min_value;
int max_value;
segTree* lef_child;
segTree* rig_child;
segTree(vector<int> (&a), int l, int r)
{
lef_index = l;
rig_index = r;
if (l==r)
{
min_value = a[l];
max_value = a[l];
lef_child = nullptr;
rig_child = nullptr;
}
else
{
int mid = (l+r)/2;
lef_child = new segTree(a, l, mid);
rig_child = new segTree(a, mid+1, r);
min_value = min(lef_child->min_value, rig_child->min_value);
max_value = max(lef_child->max_value, rig_child->max_value);
}
}
int get_min(int l, int r)
{
int lef_overlap = max(l, lef_index);
int rig_overlap = min(r, rig_index);
if ((lef_overlap == lef_index) and (rig_overlap == rig_index))
return min_value;
if (lef_overlap > rig_overlap)
return INF;
return min(lef_child->get_min(l, r), rig_child->get_min(l, r));
}
int get_max(int l, int r)
{
int lef_overlap = max(l, lef_index);
int rig_overlap = min(r, rig_index);
if ((lef_overlap == lef_index) and (rig_overlap == rig_index))
return max_value;
if (lef_overlap > rig_overlap)
return NINF;
return max(lef_child->get_max(l, r), rig_child->get_max(l, r));
}
};
int solve_query(int sloc, int eloc, int l, int r, segTree (&ST))
{
if (sloc < eloc)
{
if (ST.get_min(sloc, eloc) >= l)
return 1;
else
{
int lo = sloc;
int hi = eloc;
while (lo!=hi)
{
int mid = (lo+hi+1)/2;
if (ST.get_min(sloc, mid) >= l)
lo = mid;
else
hi = mid-1;
}
//must be able to turn to wolf at lo
if (ST.get_max(lo, eloc) <= r)
return 1;
return 0;
}
}
else
{
if (ST.get_min(eloc, sloc) >= l)
return 1;
else
{
int lo = eloc;
int hi = sloc;
while (lo!=hi)
{
//finding the lowest value I can remain human in
int mid = (lo+hi)/2;
if (ST.get_min(mid, sloc) >= l)
hi = mid;
else
lo = mid+1;
}
//must be able to turn to wolf at lo
if (ST.get_max(eloc, lo) <= r)
return 1;
return 0;
}
}
}
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) {
//preprocessing
vector<vector<int>> edges(N);
int M = X.size();
for (int i=0; i<M; i++)
{
int x = X[i];
int y = Y[i];
edges[x].push_back(y);
edges[y].push_back(x);
}
//create the line graph
int leaf = -1;
for (int i=0; i<N; i++)
if (edges[i].size() == 1)
leaf = i;
vector<int> line;
int prev = leaf;
int curr = edges[leaf][0];
line.push_back(leaf);
line.push_back(curr);
while (edges[curr].size() == 2)
{
int nex;
for (int i: edges[curr])
if (i!=prev)
nex = i;
line.push_back(nex);
prev = curr;
curr = nex;
}
vector<int> refs(N);
for (int i=0; i<N; i++)
refs[line[i]] = i;
segTree ST = segTree(line, 0, N-1);
int Q = S.size();
std::vector<int> answers(Q);
for (int i = 0; i < Q; i++) {
int l = L[i];
int r = R[i];
int s = S[i];
int e = E[i];
int sloc = refs[s];
int eloc = refs[e];
answers[i] = solve_query(sloc, eloc, l, r, ST);
}
return answers;
}
