#include "werewolf.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,M,K,Q,prosli[200005],pvred,mesto[200005],niz[200005],stmax[525000],stmin[525000];
vector<int> graf[200005],ret;
struct kveri{
int poc,kraj,id;
ll L,R;
} upiti[200005];
void dfs2(int gde,int dub){
prosli[gde]=pvred;
mesto[gde]=dub;
niz[dub]=gde;
for(int i=0;i<graf[gde].size();i++)
if(prosli[graf[gde][i]]!=pvred)
dfs2(graf[gde][i],dub+1);
return;
}
ll getmax(int gde,int lg,int dg,int lc,int dc){
return maxst[gde];
if(lg==lc and dg==dc)
return stmax[gde];
int sred=(lc+dc)/2;
if(dg<=sred)
return getmax(gde*2,lg,dg,lc,sred);
if(lg>sred)
return getmax(gde*2+1,lg,dg,sred+1,dc);
return max(getmax(gde*2,lg,sred,lc,sred),getmax(gde*2+1,sred+1,dg,sred+1,dc));
}
ll getmin(int gde,int lg,int dg,int lc,int dc){
return minst[gde];
if(lg==lc and dg==dc)
return stmin[gde];
int sred=(lc+dc)/2;
if(dg<=sred)
return getmin(gde*2,lg,dg,lc,sred);
if(lg>sred)
return getmin(gde*2+1,lg,dg,sred+1,dc);
return min(getmin(gde*2,lg,sred,lc,sred),getmin(gde*2+1,sred+1,dg,sred+1,dc));
}
vector<int> check_validity(int NN, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
N=NN;
M=X.size();
Q=L.size();
ret.resize(Q);
for(int i=0;i<M;i++){
X[i]++;
Y[i]++;
graf[X[i]].push_back(Y[i]);
graf[Y[i]].push_back(X[i]);
}
for(int i=0;i<Q;i++){
S[i]++;
E[i]++;
L[i]++;
R[i]++;
upiti[i+1].id=i;
upiti[i+1].poc=S[i];
upiti[i+1].kraj=E[i];
upiti[i+1].L=L[i];
upiti[i+1].R=R[i];
}
for(int i=1;i<=N;i++)
if(graf[i].size()==1){
dfs2(i,1);
break;
}
K=1;
while(K<N)
K<<=1;
for(int i=1;i<=N;i++)
stmin[i+K-1]=stmax[i+K-1]=niz[i];
for(int i=N+K;i<=K+K;i++)
stmin[i]=1e9;
for(int i=K-1;i>=1;i--){
stmax[i]=max(stmax[i*2],stmax[i*2+1]);
stmin[i]=min(stmin[i*2],stmin[i*2+1]);
}
ll lg,dg,sred,v,m;
for(int j=1;j<=Q;j++){
lg=mesto[upiti[j].poc];
dg=mesto[upiti[j].kraj];
if(lg==dg){
ret[upiti[j].id]=1;
continue;
}
if(lg<dg){
while(lg<=dg){
sred=(lg+dg)/2;
v=getmax(1,mesto[upiti[j].poc],sred,1,K);
m=getmin(1,sred,mesto[upiti[j].kraj],1,K);
if(v>=upiti[j].L and m<=upiti[j].R){
ret[upiti[j].id]=1;
break;
}
if(v<upiti[j].L and m>upiti[j].R)
break;
if(v>=upiti[j].L)
lg=sred+1;
else
dg=sred-1;
}
continue;
}
swap(lg,dg);
while(lg<=dg){
sred=(lg+dg)/2;
v=getmax(1,sred,mesto[upiti[j].poc],1,K);
m=getmin(1,mesto[upiti[j].kraj],sred,1,K);
if(v>=upiti[j].L and m<=upiti[j].R){
ret[upiti[j].id]=1;
break;
}
if(v<upiti[j].L and m>upiti[j].R)
break;
if(v>=upiti[j].L)
lg=sred+1;
else
dg=sred-1;
}
}
return ret;
}
Compilation message
werewolf.cpp: In function 'void dfs2(int, int)':
werewolf.cpp:15:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for(int i=0;i<graf[gde].size();i++)
| ~^~~~~~~~~~~~~~~~~
werewolf.cpp: In function 'long long int getmax(int, int, int, int, int)':
werewolf.cpp:21:11: error: 'maxst' was not declared in this scope
21 | return maxst[gde];
| ^~~~~
werewolf.cpp: In function 'long long int getmin(int, int, int, int, int)':
werewolf.cpp:32:10: error: 'minst' was not declared in this scope
32 | return minst[gde];
| ^~~~~
