#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);
vector<int> p(n + 1);
for (int i = 1; i <= n; i++){
p[a[i]] = i;
}
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 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 = p[s[i]], v = p[e[i]];
pii A, B;
int l1 = u, r1 = n;
while (l1 + 1 < r1){
int m = (l1 + r1) / 2;
int k = get_min(u, m);
if (k < l[i]){
r1 = m - 1;
}
else {
l1 = m;
}
}
if (get_min(u, r1) >= l[i]) l1 = r1;
int l2 = 1, r2 = u;
while (l1 + 1 < r1){
int m = (l2 + r2) / 2;
int k = get_min(m, u);
if (k < l[i]){
l2 = m + 1;
}
else {
r2 = m;
}
}
if (get_min(l2, u) >= l[i]) r2 = l2;
A = {r2, l1};
l1 = v; r1 = n;
while (l1 + 1 < r1){
int m = (l1 + r1) / 2;
int k = get_max(v, m);
if (k > r[i]){
r1 = m - 1;
}
else {
l1 = m;
}
}
if (get_max(v, r1) <= r[i]) l1 = r1;
l2 = 1; r2 = v;
while (l1 + 1 < r1){
int m = (l2 + r2) / 2;
int k = get_max(m, v);
if (k > r[i]){
l2 = m + 1;
}
else {
r2 = m;
}
}
if (get_max(l2, v) <= r[i]) r2 = l2;
B = {r2, l1};
out.pb(inter(A, B));
}
return out;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
668 ms |
87368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
