이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>
#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
#define int ll
using namespace std;
typedef long long ll;
typedef long double ld;
vector<int> tree_l;
vector<int> tree_r;
int N = 1;
int inf = 1e9;
void upd_l(int v) {
if(v == 0)
return;
tree_l[v] = min(tree_l[v * 2], tree_l[v * 2 + 1]);
upd_l(v / 2);
}
void upd_r(int v) {
if(v == 0)
return;
tree_r[v] = max(tree_r[v * 2], tree_r[v * 2 + 1]);
upd_r(v / 2);
}
int get_l(int v, int l, int r, int vl, int vr) {
if(vr <= l || r <= vl)
return inf;
if(vl <= l && r <= vr)
return tree_l[v];
int m = (l + r) / 2;
return min(get_l(v * 2, l, m, vl, vr), get_l(v * 2 + 1, m, r, vl, vr));
}
int get_r(int v, int l, int r, int vl, int vr) {
if(vr <= l || r <= vl)
return -inf;
if(vl <= l && r <= vr)
return tree_r[v];
int m = (l + r) / 2;
return max(get_r(v * 2, l, m, vl, vr), get_r(v * 2 + 1, m, r, vl, vr));
}
signed main() {
#ifdef PC
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
while(N < (n + 1))
N *= 2;
tree_l = vector<int> (2 * N, inf);
tree_r = vector<int> (2 * N, -inf);
vector<int> per(n);
vector<vector<int>> keys(n);
vector<vector<int>> types(n);
vector<int> l(n);
for (int i = 1; i < n; i++) {
cin >> per[i];
per[i]--;
}
for (int i = 0; i < n; i++) {
int k;
cin >> k;
for (int j = 0; j < k; j++) {
int x;
cin >> x;
x--;
types[x].pb(i);
keys[i].pb(x);
}
}
//calc v<>l
for (int i = 0; i < n; i++) {
l[i] = i;
int ln = i;
while(1) {
bool flag = 1;
ln = min(ln, get_l(1, 0, N, ln, i + 1));
if(ln > 0) {
auto uk = lower_bound(types[per[ln]].begin(), types[per[ln]].end(), ln);
if(uk != types[per[ln]].end() && (*uk <= i)) {
ln--;
flag = 0;
}
}
if(flag)
break;
}
l[i] = ln;
tree_l[N + i] = l[i];
upd_l((N + i) / 2);
}
// calc ans
vector<pair<int, int>> ans(n);
for (int i = n - 1; i >= 0; i--) {
int ln = i, rn = i + 1;
while(1) {
bool flag = 1;
ln = min(ln, get_l(1, 0, N, ln, rn));
rn = max(rn, get_r(1, 0, N, ln, rn));
if(ln > 0) {
auto uk = lower_bound(types[per[ln]].begin(), types[per[ln]].end(), ln);
if(uk != types[per[ln]].end() && (*uk < rn)) {
ln--;
flag = 0;
}
}
if(rn < n) {
auto uk = lower_bound(types[per[rn]].begin(), types[per[rn]].end(), rn);
if(uk != types[per[rn]].begin()) {
uk--;
if(*uk >= ln) {
rn++;
flag = 0;
}
}
}
if(flag)
break;
}
ans[i] = {ln, rn - 1};
tree_l[N + i] = ans[i].ft;
tree_r[N + i] = ans[i].sc + 1;
upd_l((N + i) / 2);
upd_l((N + i) / 2);
// cout << i << " " << ans[i].ft << " " << ans[i].sc << endl;
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int a, b;
cin >> a >> b;
a--, b--;
if(ans[a].ft <= b && b <= ans[a].sc)
cout << "YES" << '\n';
else
cout << "NO" << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |