#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i < b; i++)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define dbg(v) cout<<"Line("<<__LINE__<<"): "<<#v<<" = "<<v<<'\n';
#define pi pair<int,int>
#define pll pair<ll,ll>
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_multiset;
const int INF = 1e9+7;
struct STreeMin{
ll n;
vector<ll> st;
STreeMin(ll n) : n(n), st(4*n+5,INF) {}
void upd(ll k, ll l, ll r, ll p, ll v){
if(l+1==r){ st[k]=v; return;}
ll mid = (l+r)/2;
if(mid>p) upd(2*k,l,mid,p,v);
else upd(2*k+1,mid,r,p,v);
st[k]=min(st[2*k],st[2*k+1]);
}
ll query(ll k, ll l, ll r, ll L, ll R){
if(l>=R||r<=L) return INF;
if(l>=L && r<=R) return st[k];
ll mid = (l+r)/2;
return min(query(2*k,l,mid,L,R),query(2*k+1,mid,r,L,R));
}
void upd(ll p, ll v){upd(1,0,n,p,v);}
ll query(ll l, ll r){return query(1,0,n,l,r);}
};
struct STreeMax{
ll n;
vector<ll> st;
STreeMax(ll n) : n(n), st(4*n+5,0) {}
void upd(ll k, ll l, ll r, ll p, ll v){
if(l+1==r){ st[k]=v; return;}
ll mid = (l+r)/2;
if(mid>p) upd(2*k,l,mid,p,v);
else upd(2*k+1,mid,r,p,v);
st[k]=max(st[2*k],st[2*k+1]);
}
ll query(ll k, ll l, ll r, ll L, ll R){
if(l>=R||r<=L) return 0;
if(l>=L && r<=R) return st[k];
ll mid = (l+r)/2;
return max(query(2*k,l,mid,L,R),query(2*k+1,mid,r,L,R));
}
void upd(ll p, ll v){upd(1,0,n,p,v);}
ll query(ll l, ll r){return query(1,0,n,l,r);}
};
#include "werewolf.h"
const int MAXN = 200000+5;
ll level[MAXN];
vector<ll> adj[MAXN];
ll orden[MAXN];
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) {
forn(i,0,SZ(X)){
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
ll iNode = -1;
for(int i = N-1; i >=0; i--){
if(SZ(adj[i])==1){ iNode=i; break; }
}
level[iNode]=0;
orden[0]=iNode;
ll nd = adj[iNode][0];
ll parent = iNode;
while(true){
level[nd]=level[parent]+1;
orden[level[nd]]=nd;
//cout<<nd<<" "<<level[nd]<<" "<<parent<<'\n';
if(SZ(adj[nd])==1) break;
ll p = nd;
nd = (parent!=adj[nd][0] ? adj[nd][0] : adj[nd][1] );
parent = p;
}
STreeMin stmin(N);
STreeMax stmax(N);
forn(i,0,N){
stmin.upd(i,orden[i]);
stmax.upd(i,orden[i]);
}
vector<int> res;
ll l,r;
ll u,v; // u to v
forn(i,0,SZ(S)){
u=min(level[S[i]],level[E[i]]);
v=min(level[S[i]],level[E[i]]);
///////////////////////////////////
//forn(j,0,N) cout<<stmin.query(j,j+1)<<" "; cout<<'\n';
///////////////////////////////////
forn(j,L[i],R[i]+1){
stmin.upd(level[j],INF);
}
forn(j,L[i],R[i]+1){
stmax.upd(level[j],0);
}
///////////////////////////////////
//forn(j,0,N) cout<<stmin.query(j,j+1)<<" "; cout<<'\n';
///////////////////////////////////
l = 0; r = N;
while(l<=r){
ll mid = (l+r)/2;
//cout<<mid<<" -> "<<stmin.query(u,min(u+mid,(ll)N-1)+1)<<'\n';
if(stmin.query(u,min(u+mid,(ll)N-1)+1)>R[i]){
l=mid+1;
}else{
r=mid-1;
}
}
ll Left = min(u+r,(ll)N-1);
l = 0; r = N;
while(l<=r){
ll mid = (l+r)/2;
if(stmax.query(max((ll)0,v-mid),v+1)<L[i]){
l=mid+1;
}else{
r=mid-1;
}
}
ll Right = max((ll)0,v-r);
//cout<<Left<<" "<<Right<<'\n';
if(Left>=Right) res.pb(1);
else res.pb(0);
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4057 ms |
44652 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
