#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int n, m, q;
int pos[200005];
int mn[200005][20];
int mx[200005][20];
int logs[200005];
vi adj[200005], order;
void dfs_ord(int u, int p) {
pos[u] = order.size();
order.push_back(u);
for (int v : adj[u]) {
if (v != p) dfs_ord(v, u);
}
}
void Build() {
for (int i = 0; i < n; i++)
for (int j = 0; j < 20; j++)
mn[i][j] = 1e9;
for (int i = 2; i <= n; i++) logs[i] = logs[i / 2] + 1;
for (int i = 0; i < n; i++)
mn[i][0] = mx[i][0] = order[i];
for (int j = 1; j < 20; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
}
}
}
int GetMax(int l, int r) {
int lg = logs[r - l + 1];
return max(mx[l][lg], mx[r - (1 << lg) + 1][lg]);
}
int GetMin(int l, int r) {
int lg = logs[r - l + 1];
return min(mn[l][lg], mn[r - (1 << lg) + 1][lg]);
}
bool check(pair<int, int> X, pair<int, int> Y) {
if (X.second < Y.first) return false;
if (Y.second < X.first) return false;
return true;
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
n = N, m = X.size(), q = S.size();
for (int i = 0; i < m; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
int st = 0;
for (int i = 0; i < n; i++) {
if (adj[i].size() == 1) st = i;
}
dfs_ord(st, -1);
Build();
vi res(q);
for (int i = 0; i < q; i++) {
pair<int, int> X = {S[i], S[i]}, Y = {E[i], E[i]};
{
int bot = 0, top = S[i] - 1;
while (bot <= top) {
int mid = bot + top >> 1;
if (GetMin(mid, S[i] - 1) >= L[i]) {
X.first = mid;
top = mid - 1;
} else bot = mid + 1;
}
}
{
int bot = S[i] + 1, top = n - 1;
while (bot <= top) {
int mid = bot + top >> 1;
if (GetMin(S[i] + 1, mid) >= L[i]) {
X.second = mid;
bot = mid + 1;
} else top = mid - 1;
}
}
{
int bot = 0, top = E[i] - 1;
while (bot <= top) {
int mid = bot + top >> 1;
if (GetMax(mid, E[i] - 1) <= R[i]) {
Y.first = mid;
top = mid - 1;
} else bot = mid + 1;
}
}
{
int bot = E[i] + 1, top = n - 1;
while (bot <= top) {
int mid = bot + top >> 1;
if (GetMax(E[i] + 1, mid) <= R[i]) {
Y.second = mid;
bot = mid + 1;
} else top = mid - 1;
}
}
res[i] = (check(X, Y) ? 1 : 0);
}
return res;
}
Compilation message
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:73:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | int mid = bot + top >> 1;
| ~~~~^~~~~
werewolf.cpp:83:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | int mid = bot + top >> 1;
| ~~~~^~~~~
werewolf.cpp:93:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
93 | int mid = bot + top >> 1;
| ~~~~^~~~~
werewolf.cpp:103:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
103 | int mid = bot + top >> 1;
| ~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
360 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
360 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
807 ms |
64736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
360 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
