#include "werewolf.h"
#include <cassert>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
#define forn(i,n) for(int i=0;i<int(n);i++)
#define SIZE(c) int((c).size())
#define ALL(c) begin(c), end(c)
#define DBG(x) cerr << #x << " = " << (x) << endl
template <typename T>
ostream & operator<<(ostream &os, const vector<T> &v)
{
os << "[";
forn(i,SIZE(v))
{
if (i > 0)
os << ",";
os << v[i];
}
os << "]";
return os;
}
const int MAXN = 210000;
const int LEVELS = 20;
int sparseTable[LEVELS][MAXN];
int neighbors[MAXN][2];
int degree[MAXN];
int rmq(int a, int b)
{
assert(a < b);
int potIndex = 31-__builtin_clz(b-a);
int pot = 1 << potIndex;
return min(sparseTable[potIndex][a], sparseTable[potIndex][b-pot]);
}
int query(int N, int s, int L) // Cuantos hay desde s que son >= L
{
// [s, a) son todos >= L
// [s, b) NO son todos >= L
int a = s;
int b = N+1;
while (b-a > 1)
{
int c = (a+b)/2;
if (rmq(s, c) >= L)
a = c;
else
b = c;
}
assert(s < a); // Por restriccion del enunciado!
return a-s;
}
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) {
const int M = SIZE(X);
forn(i,N)
forn(k,2)
neighbors[i][k] = -1;
forn(i, M)
{
#define ADD_NEIGHBOR(a,b) do {assert(degree[a] < 2); neighbors[a][degree[a]++] = (b); } while (false)
ADD_NEIGHBOR(X[i],Y[i]);
ADD_NEIGHBOR(Y[i],X[i]);
}
vector<int> nodes(N);
forn(i, N)
if (degree[i] == 1)
{
int current = i;
int last = neighbors[current][1];
forn(j,N)
{
nodes[j] = current;
int oldCurrent = current;
current = neighbors[current][0] ^ neighbors[current][1] ^ last;
last = oldCurrent;
}
goto taTodoReBien;
}
assert(false);
taTodoReBien:;
map<int,int> indices;
forn(i,N)
indices[nodes[i]] = i;
int Q = SIZE(S);
forn(i,Q) // TRADUZCO LA QUERIES, OJO CON EL CUADRATICO
{
S[i] = indices[S[i]];
E[i] = indices[E[i]];
}
vector<int> ret(Q, 0);
forn(reversedPass,2) // S < E S > E
{
forn(pass,2) // S,L N-1-E, -R, array flipeado
{
forn(i,N)
sparseTable[0][i] = nodes[i];
forn(i,LEVELS-1)
forn(j,N-(1<<(i+1))+1)
sparseTable[i+1][j] = min(sparseTable[i][j], sparseTable[i][j+(1<<i)]);
forn(i,Q)
if (S[i] < E[i])
{
if (pass == 0)
ret[i] += query(N, S[i], L[i]);
else
ret[i] += query(N, N-1-E[i], -R[i]);
}
reverse(ALL(nodes));
forn(i,SIZE(nodes))
nodes[i] = -nodes[i];
}
reverse(ALL(nodes));
forn(i,Q)
{
S[i] = N-1-S[i];
E[i] = N-1-E[i];
}
}
forn(i,Q)
ret[i] = ret[i] > abs(E[i] - S[i])+1;
return ret;
}
