#include "werewolf.h"
#include <bits/stdc++.h>
#ifdef ALE
#include "grader.cpp"
#endif
#define f first
#define s second
#define debug cout<<"ok"<<endl
using namespace std;
const int nax=2e5+5;
vector<int> grafo[nax];
vector<int> l;
bitset<nax> v;
int f[nax];
int ind[nax];
int pos[nax];
pair<int,int> ans[nax];
int Ni;
void update(int k){
k++;
while(k<=Ni){
f[k]++;
k+=k&(-k);
}
}
int query(int k){
if(k<0)return 0;
k++;
int sol=0;
while(k>0){
sol+=f[k];
k-=k&(-k);
}
return sol;
}
int leftmost(int u, int v){
int sol=u-1;
int q=query(u-1);
for(int b=v-u;b>=1;b/=2)
while(sol+b<=v&&query(sol+b)==q)sol+=b;
return sol+1;
}
int rightmost(int u, int v){
int sol=v+1;
int q=query(v);
for(int b=v-u;b>=1;b/=2)
while(sol-b>=u&&query(sol-b-1)==q)sol-=b;
return sol-1;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
Ni=N;
int Q = S.size();
int M=X.size();
vector<int> A(Q);
int ini=-1;
for(int i=0;i<M;i++){
grafo[X[i]].push_back(Y[i]);
grafo[Y[i]].push_back(X[i]);
}
for(int i=0;i<N;i++)
if(grafo[i].size()==1){
ini=i;
break;
}
while(ini!=-1){
v[ini]=1;
ind[ini]=l.size();
l.push_back(ini);
if(!v[grafo[ini][0]])ini=grafo[ini][0];
else if(grafo[ini].size()>1)ini=grafo[ini][1];
else ini=-1;
}
//-------------
auto cmpl=[&](int x,int y){
return L[x]<L[y];
};
auto cmpr=[&](int x, int y){
return R[x]>R[y];
};
iota(pos,pos+Q,0);
sort(pos,pos+Q,cmpl);
int j=0;
for(int i=0;i<Q;i++){
int x=pos[i];
while(j<N&&j<L[x])update(ind[j++]);
if(ind[S[x]]<ind[E[x]]){
ans[i].f=leftmost(ind[S[x]],ind[E[x]]);
}else ans[i].f=rightmost(ind[E[x]],ind[S[x]]);
}
iota(pos,pos+Q,0);
sort(pos,pos+Q,cmpr);
for(int i=0;i<=N;i++)f[i]=0;
j=N-1;
for(int i=0;i<Q;i++){
int x=pos[i];
while(j>=0&&j>R[x])update(ind[j--]);
if(ind[S[x]]<ind[E[x]]){
ans[i].s=rightmost(ind[S[x]],ind[E[x]]);
}else ans[i].s=leftmost(ind[E[x]],ind[S[x]]);
}
//----------------------------
for(int q=0;q<Q;q++){
int s=ind[S[q]],e=ind[E[q]];
if(s<e){
if(ans[q].f<ans[q].s)A[q]=0;
else if(ans[q].s+1==ans[q].f)A[q]=0;
else A[q]=1;
}else{
if(ans[q].f>ans[q].s)A[q]=0;
else if(ans[q].f+1==ans[q].s)A[q]=0;
else A[q]=1;
}
}
return A;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
567 ms |
26336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
