#include "werewolf.h"
#include<bits/stdc++.h>
#define ll long long
#define fr fisrt
#define se second
#define pb push_back
using namespace std;
const ll M = 1e5 + 1;
int trmx[4*M];
int trmn[4*M];
vector<int>g[M];
int d[M], a[M], t;
void dfs( int v, int p )
{
d[v] = t ++;
for( auto to: g[v] )
if( to != p )
dfs( to, v );
}
void bld( int v, int tl, int tr )
{
if( tl == tr )
trmx[v] = trmn[v] = a[tl];
else
{
int tm = (tl + tr) / 2;
bld( v*2, tl, tm );
bld( v*2+1, tm+1, tr );
trmx[v] = max( trmx[v*2], trmx[v*2+1] );
trmn[v] = min( trmn[v*2], trmn[v*2+1] );
}
}
int get_mx( int v, int tl, int tr, int l, int r )
{
if( l > r )
return 0;
if( tl == l && tr == r )
return trmx[v];
int tm = (tl + tr) / 2;
return max( get_mx( v*2, tl, tm, l, min(tm, r) ), get_mx( v*2+1, tm+1, tr, max(tm+1, l), r ) );
}
int get_mn( int v, int tl, int tr, int l, int r )
{
if( l > r )
return 1e8;
if( tl == l && tr == r )
return trmn[v];
int tm = (tl + tr) / 2;
return min( get_mn( v*2, tl, tm, l, min(tm, r) ), get_mn( v*2+1, tm+1, tr, max(tm+1, l), r ) );
}
int g_max( int l, int r, int n )
{
return get_mx( 1, 0, n-1, l, r );
}
int g_min( int l, int r, int n )
{
return get_mn( 1, 0, n-1, l, r );
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int Q = S.size();
vector<int> A(Q);
for( int i = 0; i < int(X.size()); i ++ )
{
g[X[i]].pb( Y[i] );
g[Y[i]].pb( X[i] );
}
int st = 0;
for( int i = 0; i < N; i ++ )
if( int(g[i].size()) == 1 )
st = i;
dfs( st, st );
for( int i = 0; i < N; i ++ )
a[d[i]] = i;
for( int i = 0; i < Q; i ++ )
{
S[i] = d[S[i]];
E[i] = d[E[i]];
if( S[i] > E[i] )
swap( S[i], E[i] );
}
for( int i = 0; i < Q; i ++ )
{
if( g_min( S[i], E[i], N ) >= L[i] && g_max( S[i], E[i], N ) <= R[i] )
{
A[i] = 1;
continue;
}
if( g_max( S[i], E[i], N ) <= R[i] )
{
if( a[S[i]] >= L[i] && a[S[i]] <= R[i] )
A[i] = 1;
else
A[i] = 0;
continue;
}
if( g_min( S[i], E[i], N ) >= L[i] )
{
if( a[E[i]] >= L[i] && a[E[i]] <= R[i] )
A[i] = 1;
else
A[i] = 0;
continue;
}
int l = S[i], r = E[i], m;
while( l < r )
{
m = (l + r) / 2;
if( g_min( S[i], m, N ) < L[i] )
r = m;
else
l = m + 1;
}
if( l == S[i] )
{
A[i] = 0;
continue;
}
if( a[l-1] < L[i] or a[i-1] > R[i] )
{
A[i] = 0;
continue;
}
if( l == E[i] )
{
A[i] = 1;
continue;
}
A[i] = g_max( l+1, E[i], N ) <= R[i];
}
return A;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
496 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
496 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
289 ms |
44252 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
496 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
