#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r){
vector<int> g[n + 1];
int m = (int) x.size();
if (m != (n - 1)) exit(0);
for (int i = 0; i < m; i++){
x[i]++; y[i]++;
g[x[i]].pb(y[i]);
g[y[i]].pb(x[i]);
}
for (int i = 0; i < n; i++){
l[i]++; r[i]++;
s[i]++; e[i]++;
}
int f = 0;
for (int i = 1; i <= n; i++){
if (g[i].size() == 1){
f = i;
break;
}
}
vector<int> a = {0};
function<void(int, int)> dfs = [&](int v, int pr){
a.pb(v);
for (int i: g[v]){
if (i != pr){
dfs(i, v);
}
}
};
dfs(f, 0);
const int lg = ceil(log2(n));
vector<vector<int>> sp1(n + 1, vector<int>(lg + 1));
vector<vector<int>> sp2 = sp1;
for (int i = 1; i <= n; i++){
sp1[i][0] = a[i];
sp2[i][0] = a[i];
}
for (int k = 1; k <= lg; k++){
for (int i = 1; i + (1 << k) <= n + 1; i++){
sp1[i][k] = min(sp1[i][k - 1], sp1[i + (1 << (k - 1))][k - 1]);
sp2[i][k] = max(sp2[i][k - 1], sp2[i + (1 << (k - 1))][k - 1]);
}
}
vector<int> log(n + 1);
for (int i = 2; i <= n; i++){
log[i] = log[i / 2] + 1;
}
auto get_min = [&](int l, int r){
int k = log[r - l + 1];
return min(sp1[l][k], sp1[r - (1 << k) + 1][k]);
};
auto get_max = [&](int l, int r){
int k = log[r - l + 1];
return max(sp2[l][k], sp2[r - (1 << k) + 1][k]);
};
auto check = [&](int x, pii& R){
return (R.ff <= x && x <= R.ss);
};
auto find = [&](int x, pii R){
int l1 = x, r1 = n;
while (l1 + 1 < r1){
int m = (l1 + r1) / 2;
if (!check(get_min(x, m), R) || !check(get_max(x, m), R)){
r1 = m - 1;
}
else {
l1 = m;
}
}
if (x <= r1 && check(get_min(x, r1), R) && check(get_max(x, r1), R)){
l1 = r1;
}
int l2 = 1, r2 = x;
while (l2 + 1 < r2){
int m = (l2 + r2) / 2;
if (!check(get_min(m, x), R) || !check(get_max(m, x), R)){
l2 = m + 1;
}
else {
r2 = m;
}
}
if (l2 <= x && check(get_min(l2, x), R) && check(get_max(l2, x), R)){
r2 = l2;
}
return make_pair(r2, l1);
};
auto inter = [&](pii A, pii B){
if (A.ff > B.ff) swap(A, B);
return (A.ss >= B.ff);
};
int q = (int) s.size();
vector<int> out;
for (int i = 0; i < q; i++){
int u = s[i], v = e[i];
pii A = find(u, {l[i], n});
pii B = find(v, {1, r[i]});
out.pb(inter(A, B));
}
return out;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1095 ms |
86556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
