#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 = 22;
const ll N_M = 4e5 + 1;
int mx[N_M][M];
int mn[N_M][M];
vector<int>g[N_M];
int d[N_M], a[N_M], s[N_M], t;
void dfs( int v, int p )
{
d[v] = t ++;
for( auto to: g[v] )
if( to != p )
dfs( to, v );
}
int g_max( int l, int r )
{
int m = d[r-l+1];
int mi = r - (1 << m) + 1;
return max( mx[l][m], mx[mi][m] );
}
int g_min( int l, int r )
{
int m = d[r-l+1];
int mi = r - (1 << m) + 1;
return min( mn[l][m], mn[mi][m] );
}
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 < M; i ++ )
{
int h = (1 << i);
if( h >= N )
break;
s[h] = 1;
}
for( int i = 1; i < N; i ++ )
s[i] += s[i-1];
for( int i = 0; i < N; i ++ )
mx[i][0] = mn[i][0] = a[i];
for( int i = 0; i < N; i ++ )
{
for( int j = 1; j < M; j ++ )
{
int h1 = (1 << j);
int h2 = (1 << (j-1));
if( i+h1-1 >= N )
break;
mx[i][j] = max( mx[i][j-1], mx[i+h2][j-1] );
mn[i][j] = min( mn[i][j-1], mn[i+h2][j-1] );
}
}
for( int i = 0; i < Q; i ++ )
{
if( g_min( S[i], E[i] ) >= L[i] && g_max( S[i], E[i] ) <= R[i] )
{
A[i] = 1;
continue;
}
if( g_max( S[i], E[i] ) <= 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] ) >= 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 ) < 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] ) <= R[i];
}
return A;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
477 ms |
524292 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 |
477 ms |
524292 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 |
474 ms |
146524 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 |
477 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
