# include <bits/stdc++.h>
# include "werewolf.h"
using namespace std;
const int N = 4e5 + 2;
int ver[N], pos[N], n, t[2][N * 4];
vector <int> g[N];
void upd(int pos, int val, int tp, int v = 1, int tl = 1, int tr = n){
if(tl == tr){
t[tp][v] = ver[tl];
} else {
int tm = (tl + tr) >> 1;
if(pos <= tm)
upd(pos, val, tp, v << 1, tl, tm);
else
upd(pos, val, tp, v << 1 | 1, tm + 1, tr);
if(tp)
t[tp][v] = max(t[tp][v << 1], t[tp][v << 1 | 1]);
else
t[tp][v] = min(t[tp][v << 1], t[tp][v << 1 | 1]);
}
}
int get(int l, int r, int tp, int v = 1, int tl = 1, int tr = n){
if(tl > r || l > tr){
if(tp)
return 0;
else
return 2e9;
}
if(l <= tl && tr <= r)
return t[tp][v];
int tm = (tl + tr) >> 1;
if(tp)
return max(get(l, r, tp, v << 1, tl, tm),
get(l, r, tp, v << 1 | 1, tm + 1, tr));
else
return min(get(l, r, tp, v << 1, tl, tm),
get(l, r, tp, v << 1 | 1, tm + 1, tr));
}
void dfs(int v, int par = -1){
ver[++ n] = v;
for(int to : g[v]){
if(to == par)
continue;
dfs(to, v);
}
}
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();
int m = X.size();
vector <int> A(q);
for(int i = 0; i < m; i ++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for(int i = 0; i < N; i ++){
if(g[i].size() == 1){
dfs(i);
break;
}
}
for(int i = 0; i < N; i ++){
pos[ver[i + 1]] = i + 1;
upd(i + 1, ver[i + 1], 0);
upd(i + 1, ver[i + 1], 1);
}
for(int i = 0; i < q; i ++){
int l1, l2, r1, r2;
l1 = pos[S[i]], r1 = pos[S[i]];
l2 = pos[E[i]], r2 = pos[E[i]];
int lo = 1, hi = l1, ret = l1;
while(lo <= hi){
int md = (lo + hi) >> 1;
if(get(md, l1, 0) >= L[i])
hi = md - 1, ret = md;
else
lo = md + 1;
}
l1 = ret;
lo = r1, hi = n;
while(lo <= hi){
int md = (lo + hi) >> 1;
if(get(r1, md, 0) >= L[i])
lo = md + 1, ret = md;
else
hi = md - 1;
}
r1 = ret;
lo = 1, hi = l2, ret = l2;
while(lo <= hi){
int md = (lo + hi) >> 1;
if(get(md, l2, 1) <= R[i])
hi = md - 1, ret = md;
else
lo = md + 1;
}
l2 = ret;
lo = r2, hi = n;
while(lo <= hi){
int md = (lo + hi) >> 1;
if(get(r2, md, 1) <= R[i])
lo = md + 1, ret = md;
else
hi = md - 1;
}
r2 = ret;
if(max(l1, l2) <= min(r1, r2))
A[i] = 1;
}
return A;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
60 ms |
59004 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 |
60 ms |
59004 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 |
Execution timed out |
4017 ms |
41408 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
60 ms |
59004 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
