#include"werewolf.h"
#include<bits/stdc++.h>
#include"grader.cpp"
#define V vector
#define node pair<int,int>
#define a first
#define b second
using namespace std;
V<int>g[200005];
int pos[200005],logs[200005],spx[200005][18],spn[200005][18];
int gt_mx(int l,int r){
int lev=logs[r-l+1];
return max(spx[l][lev],spx[r-(1<<lev)+1][lev]);
}
int gt_mn(int l,int r){
int lev=logs[r-l+1];
return min(spn[l][lev],spn[r-(1<<lev)+1][lev]);
}
bool check(int l,int r,int nl,int nr){
if(l>r)swap(l,r);
return gt_mn(l,r)>=nl&>_mx(l,r)<=nr;
}
node t[200005 * 4],cr;
node combine(node a,node b) {
a.a = max(a.a,b.a);
a.b = min(a.b,b.b);
return a;
}
void build (int v ,int tl,int tr) {
if (tl == tr) {
t[v].a = t[v].b = spx[tl][0];
}
else {
int tm = (tl + tr) >> 1;
build (v + v,tl,tm);
build (v + v + 1,tm + 1,tr);
t[v] = combine(t[v + v],t[v + v + 1]);
}
}
node get (int l,int r,int v ,int tl ,int tr ) {
if (tl > r || tr < l) return {0,2e9};
if (l <= tl && tr <= r) return t[v];
int tm = (tl + tr) >> 1;
return combine(get(l,r,v + v,tl,tm),get(l,r,v + v + 1,tm + 1,tr));
}
V<int>check_validity(int n,V<int>x,V<int>y,V<int>S,V<int>E,V<int>L,V<int>R){
int root,i,j;
for(i=2;i<=n;i++)logs[i]=logs[i>>1]+1;
V<int>res;
for(i=0;i<x.size();i++){
x[i]++;
y[i]++;
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
for(i=1;i<=n;i++)if(g[i].size()==1)root=i;
spx[1][0]=root;
spn[1][0]=root;
pos[root]=1;
int p=root;
for(i=2;i<=n;i++){
if(g[root][0]!=p){
p=root;
root=g[root][0];
}else{
p=root;
root=g[root][1];
}
spx[i][0]=root;
spn[i][0]=root;
pos[root]=i;
}
for(j=1;j<18;j++){
for(i=1;i+(1<<j)-1<=n;i++)spn[i][j]=min(spn[i][j-1],spn[i+(1<<(j-1))][j-1]);
for(i=1;i+(1<<j)-1<=n;i++)spx[i][j]=max(spx[i][j-1],spx[i+(1<<(j-1))][j-1]);
}
build(1,1,n);
for(int i=0;i<S.size();i++){
int l=pos[S[i]+1],r=pos[E[i]+1],s=L[i]+1,e=R[i]+1;
if(l<=r){
int mxl=n,mnr=1;
while(l<mxl){
int mid=(l+mxl+1)>>1;
if(check(pos[S[i]+1],mid,s,n))l=mid;
else mxl=mid-1;
}
while(mnr<r){
int mid=(mnr+r)>>1;
if(check(mid,pos[E[i]+1],1,e))r=mid;
else mnr=mid+1;
}
res.push_back(mxl>=mnr);
}else{
int lo = r,hi = l;
while (hi - lo > 1) {
int md = (hi + lo) >> 1;
cr = get(pos[E[i]+1],md,1,1,n);
if (cr.a <= e) lo = md;
else hi = md;
}
cr = get(pos[E[i]+1],hi,1,1,n);
if (cr.a <= e) lo = hi;
l = pos[E[i]+1],r = pos[S[i]+1];
while (r - l > 1) {
int md = (r + l) >> 1;
cr = get(md,pos[S[i]+1],1,1,n);
if (cr.b >= s) r = md;
else l = md;
}
cr = get(l,pos[S[i]+1],1,1,n);
if (cr.b >= s) r = l;
res.push_back(r <= lo);
}
}
return res;
}
/*
10 9 10
6 7
1 5
8 0
2 9
9 4
2 7
8 5
6 0
3 4
4 9 0 9
8 1 8 9
1 8 1 8
8 3 5 5
8 9 3 9
0 1 0 2
9 0 6 6
1 7 1 8
9 4 5 6
9 5 0 9
/*
1
1
1
0
1
1
0
1
0
1
*/
Compilation message
werewolf.cpp:162:1: warning: "/*" within comment [-Wcomment]
162 | /*
|
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:71:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(i=0;i<x.size();i++){
| ~^~~~~~~~~
werewolf.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i=0;i<S.size();i++){
| ~^~~~~~~~~
werewolf.cpp:78:14: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
78 | spx[1][0]=root;
| ~~~~~~~~~^~~~~
/tmp/ccEiAMb1.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccRl1ko2.o:werewolf.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
