#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int n, m, q;
int mx[800005];
int mn[800005];
vi adj[200005], order;
void dfs_ord(int u, int p) {
order.push_back(u);
for (int v : adj[u]) {
if (v != p) dfs_ord(v, u);
}
}
void Build(int node, int l, int r) {
if (l == r) {
mx[node] = order[l];
mn[node] = order[l];
return;
}
int mid = l + r >> 1;
Build(node * 2, l, mid);
Build(node * 2 + 1, mid + 1, r);
mx[node] = max(mx[node * 2], mx[node * 2 + 1]);
mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
}
int GetMax(int node, int l, int r, int ll, int rr) {
if (l > r || l > rr || r < ll) return 0;
if (ll <= l && r <= rr) return mx[node];
int mid = l + r >> 1;
return max(GetMax(node * 2, l, mid, ll, rr), GetMax(node * 2 + 1, mid + 1, r, ll, rr));
}
int GetMin(int node, int l, int r, int ll, int rr) {
if (l > r || l > rr || r < ll) return 1e9;
if (ll <= l && r <= rr) return mn[node];
int mid = l + r >> 1;
return min(GetMin(node * 2, l, mid, ll, rr), GetMin(node * 2 + 1, mid + 1, r, ll, rr));
}
bool check(pair<int, int> X, pair<int, int> Y) {
if (X.first <= Y.first && Y.second <= X.second) return true;
if (Y.first <= X.first && X.second <= Y.second) return true;
if (X.first <= Y.second && Y.first <= X.first) return true;
if (Y.first <= X.second && X.first <= Y.first) return true;
return false;
}
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(1, 0, n - 1);
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(1, 0, n - 1, 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(1, 0, n - 1, 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(1, 0, n - 1, 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(1, 0, n - 1, 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 'void Build(int, int, int)':
werewolf.cpp:24:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
24 | int mid = l + r >> 1;
| ~~^~~
werewolf.cpp: In function 'int GetMax(int, int, int, int, int)':
werewolf.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | int mid = l + r >> 1;
| ~~^~~
werewolf.cpp: In function 'int GetMin(int, int, int, int, int)':
werewolf.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | int mid = l + r >> 1;
| ~~^~~
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:71:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | int mid = bot + top >> 1;
| ~~~~^~~~~
werewolf.cpp:81:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
81 | int mid = bot + top >> 1;
| ~~~~^~~~~
werewolf.cpp:91:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
91 | int mid = bot + top >> 1;
| ~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
365 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
365 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3757 ms |
35880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
365 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
