이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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
#define arr3 array<int, 3>
struct ST{
vector<pii> t;
vector<int> a;
int n;
ST(int ns){
n = ns;
t.resize(4 * n);
a.resize(n + 1);
}
void upd(int v, int tl, int tr, int& p, int& x){
if (tl == tr){
t[v] = {x, x};
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
if (p <= tm){
upd(vv, tl, tm, p, x);
}
else {
upd(vv + 1, tm + 1, tr, p, x);
}
t[v].ff = min(t[vv].ff, t[vv + 1].ff);
t[v].ss = max(t[vv].ss, t[vv + 1].ss);
}
void upd(int p, int x){
upd(1, 1, n, p, x);
a[p] = x;
}
vector<arr3> all;
void dec(int v, int tl, int tr, int& l, int& r){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
all.pb({v, tl, tr});
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
dec(vv, tl, tm, l, r);
dec(vv + 1, tm + 1, tr, l, r);
}
int fn1(int v, int tl, int tr, int& x){
if (tl == tr) return (tl - (a[tl] <= x));
int tm = (tl + tr) / 2, vv = 2 * v;
if (t[vv + 1].ss > x){
return fn1(vv + 1, tm + 1, tr, x);
}
return fn1(vv, tl, tm, x);
}
int find1(int l, int r, int x){
if (l > r || a[r] > x) return -1;
all.clear();
dec(1, 1, n, l, r);
reverse(all.begin(), all.end());
for (auto [v, tl, tr]: all){
if (t[v].ss > x){
return fn1(v, tl, tr, x) + 1;
}
}
return l;
}
int fn2(int v, int tl, int tr, int& x){
if (tl == tr) return tl + (a[tl] >= x);
int tm = (tl + tr) / 2, vv = 2 * v;
if (t[vv].ff < x){
return fn2(vv, tl, tm, x);
}
return fn2(vv + 1, tm + 1, tr, x);
}
int find2(int l, int r, int x){
if (l > r || a[l] < x) return -1;
all.clear();
dec(1, 1, n, l, r);
for (auto [v, tl, tr]: all){
if (t[v].ff < x){
return fn2(v, tl, tr, x) - 1;
}
}
return r;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n; cin>>n;
vector<int> c(n);
for (int i = 1; i < n; i++){
cin>>c[i];
}
vector<int> A[n + 1];
for (int i = 1; i <= n; i++){
int x; cin>>x;
while (x--){
int y; cin>>y;
A[i].pb(y);
}
}
vector<int> x(n), lst(n + 1, n + 1);
for (int i = n; i > 0; i--){
if (i < n){
x[i] = lst[c[i]];
}
for (int j: A[i]){
lst[j] = i;
}
}
fill(lst.begin(), lst.end(), 0);
vector<int> y(n);
for (int i = 1; i < n; i++){
for (int j: A[i]){
lst[j] = i;
}
y[i] = lst[c[i]];
}
ST T1(n - 1), T2(n - 1);
for (int i = 1; i < n; i++){
T1.upd(i, x[i]);
T2.upd(i, y[i]);
}
map<pii, pii> mp;
function<pii(int, int)> solve = [&](int l, int r){
int l1 = l, r1 = r;
bool ind1 = 0, ind2 = 0;
int j = T1.find1(1, l - 1, r);
if (j != -1){
l = j;
ind1 = 1;
}
j = T2.find2(r, n - 1, l);
if (j != -1){
r = j + 1;
ind2 = 1;
}
if (!ind1 && !ind2){
mp[{l, r}] = {l, r};
return make_pair(l, r);
}
pii x = solve(l, r);
mp[{l1, r1}] = x;
return x;
};
vector<pii> rr(n + 1);
for (int i = 1; i <= n; i++){
solve(i, i);
rr[i] = mp[{i, i}];
}
int Q; cin>>Q;
while (Q--){
int x, y; cin>>x>>y;
cout<<((rr[x].ff <= y && y <= rr[x].ss) ? "YES" : "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... |