제출 #1096945

#제출 시각아이디문제언어결과실행 시간메모리
1096945vladiliusLong Mansion (JOI17_long_mansion)C++17
25 / 100
3066 ms85068 KiB
#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]); } vector<pii> rr(n + 1); for (int i = 1; i <= n; i++){ int l = i, r = i; while (true){ 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) break; } rr[i] = {l, r}; } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...