#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
//0: human can reach (max) 1: werewolf (min)
const int N=600050;
int n,ch[2][2][N],val[2][N],par[2][N],pt[2],lift[2][20][N],sz[2][N],tim[2],pre[2][N],bit[N];
int u,v,l0,r0,l1,r1;
vector<pair<int,pair<int,int>>> srt[2];
vector<pair<pair<int,int>,pair<int,int>>> op;
int find(int id,int nde){
return par[id][nde]==nde?nde:par[id][nde]=find(par[id][nde]);
}
void dfs(int id,int nde,int par){
lift[id][0][nde]=par;
for (int i=1;i<=19;i++) lift[id][i][nde]=lift[id][i-1][lift[i-1][nde]];
pre[id][nde]=++tim[id];
sz[id][nde]=1;
if (nde>=n){
dfs(id,ch[id][0][nde],nde);
dfs(id,ch[id][1][nde],nde);
sz[id][nde]+=sz[id][ch[id][0][nde]]+sz[id][ch[id][1][nde]];
}
}
void upd(int id,int val){
for (;id<N;id+=id&-id) bit[id]+=val;
}
int query(int id){
int ret=0;
for (;id;id-=id&-id) ret+=bit[id];
return ret;
}
vector<int> check_validity(int N, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
n=N;
int q=s.size(),m=x.size();
vector<int> ans(q);
for (int i=0;i<m;i++){
srt[0].push_back({min(x[i],y[i]),{x[i],y[i]}});
srt[1].push_back({max(x[i],y[i]),{x[i],y[i]}});
}
sort(srt[0].begin(),srt[0].end(),greater<pair<int,pair<int,int>>>());
sort(srt[1].begin(),srt[1].end());
for (int i=0;i<2*n;i++) par[0][i]=par[1][i]=i;
pt[0]=n,pt[1]=n;
for (auto i:srt[0]){
if (find(0,i.second.first)==find(0,i.second.second)) continue;
ch[0][0][pt[0]]=find(0,i.second.first);
ch[0][1][pt[0]]=find(0,i.second.second);
par[0][find(0,i.second.first)]=pt[0];
par[0][find(0,i.second.second)]=pt[0];
val[0][pt[0]]=i.first;
pt[0]++;
}
for (auto i:srt[1]){
if (find(1,i.second.first)==find(1,i.second.second)) continue;
ch[1][0][pt[1]]=find(1,i.second.first);
ch[1][1][pt[1]]=find(1,i.second.second);
par[1][find(1,i.second.first)]=pt[1];
par[1][find(1,i.second.second)]=pt[1];
val[1][pt[1]]=i.first;
pt[1]++;
}
dfs(0,2*n-2,2*n-2);
dfs(1,2*n-2,2*n-2);
for (int i=0;i<n;i++) op.push_back({{pre[0][i],pre[1][i]},{1,1}});
for (int i=0;i<q;i++){
u=s[i],v=e[i];
for (int j=19;j>=0;j--) if (val[0][lift[0][j][u]]>=l[i]) u=lift[0][j][u];
for (int j=19;j>=0;j--) if (val[1][lift[1][j][v]]<=r[i]) v=lift[1][j][v];
l0=pre[0][u],r0=pre[0][u]+sz[0][u]-1;
l1=pre[1][v],r1=pre[1][v]+sz[1][v]-1;
op.push_back({{r0,r1},{2,i*2}});
op.push_back({{r0,l1-1},{2,i*2+1}});
op.push_back({{l0-1,r1},{2,i*2+1}});
op.push_back({{l0-1,l1-1},{2,i*2}});
}
sort(op.begin(),op.end());
for (auto i:op){
if (i.second.first==1){
upd(i.first.second,1);
}else if (i.second.first==2){
if (i.second.second%2) ans[i.second.second/2]-=query(i.first.second);
else ans[i.second.second/2]+=query(i.first.second);
}else{
upd(i.first.second,-1);
}
}
for (int &i:ans) i=!!i;
return ans;
}
Compilation message
werewolf.cpp: In function 'int find(int, int)':
werewolf.cpp:11:61: error: no matching function for call to 'find(int&)'
11 | return par[id][nde]==nde?nde:par[id][nde]=find(par[id][nde]);
| ^
werewolf.cpp:10:5: note: candidate: 'int find(int, int)'
10 | int find(int id,int nde){
| ^~~~
werewolf.cpp:10:5: note: candidate expects 2 arguments, 1 provided
In file included from /usr/include/c++/10/bits/locale_facets.h:48,
from /usr/include/c++/10/bits/basic_ios.h:37,
from /usr/include/c++/10/ios:44,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from werewolf.cpp:2:
/usr/include/c++/10/bits/streambuf_iterator.h:422:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT> >::__type std::find(std::istreambuf_iterator<_CharT>, std::istreambuf_iterator<_CharT>, const _CharT2&)'
422 | find(istreambuf_iterator<_CharT> __first,
| ^~~~
/usr/include/c++/10/bits/streambuf_iterator.h:422:5: note: template argument deduction/substitution failed:
werewolf.cpp:11:61: note: mismatched types 'std::istreambuf_iterator<_CharT>' and 'int'
11 | return par[id][nde]==nde?nde:par[id][nde]=find(par[id][nde]);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from werewolf.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3894:5: note: candidate: 'template<class _IIter, class _Tp> _IIter std::find(_IIter, _IIter, const _Tp&)'
3894 | find(_InputIterator __first, _InputIterator __last,
| ^~~~
/usr/include/c++/10/bits/stl_algo.h:3894:5: note: template argument deduction/substitution failed:
werewolf.cpp:11:61: note: candidate expects 3 arguments, 1 provided
11 | return par[id][nde]==nde?nde:par[id][nde]=find(par[id][nde]);
| ^
werewolf.cpp: In function 'void dfs(int, int, int)':
werewolf.cpp:15:56: error: invalid types 'int [600050][int [600050]]' for array subscript
15 | for (int i=1;i<=19;i++) lift[id][i][nde]=lift[id][i-1][lift[i-1][nde]];
| ^
