제출 #1209870

#제출 시각아이디문제언어결과실행 시간메모리
1209870HanksburgerLong Mansion (JOI17_long_mansion)C++20
100 / 100
492 ms89100 KiB
#include <bits/stdc++.h> using namespace std; int c[500005], d[500005], e[500005], X[500005], Y[500005], bit[500005], ans[500005], n, q; vector<pair<pair<int, int>, pair<int, int> > > event; vector<int> a[500005], store[500005]; void update(int x, int y) { for (int i=x; i<=n; i+=i&(-i)) bit[i]+=y; } int query(int x) { int res=0; for (int i=x; i; i-=i&(-i)) res+=bit[i]; return res; } void solve(int t) { for (int i=1; i<=n; i++) bit[i]=0; sort(event.begin(), event.end()); int ind=0; set<int> s; for (int i=1; i<=n; i++) { while (ind<event.size() && event[ind].first.first==i) { if (event[ind].first.second) { if (query(event[ind].second.first-1)==query(event[ind].second.second)) ans[event[ind].first.second]=1; } else if (event[ind].second.first) { if (t) { while (s.size() && *prev(s.end())>=event[ind].second.second) { update(*prev(s.end()), 1); s.erase(prev(s.end())); } } else { while (s.size() && *s.begin()<=event[ind].second.second) { update(*s.begin(), 1); s.erase(s.begin()); } } } else s.insert(event[ind].second.second); ind++; } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i=1; i<n; i++) cin >> c[i]; for (int i=1; i<=n; i++) { int m; cin >> m; while (m--) { int x; cin >> x; a[i].push_back(x); } d[i]=n+1; } for (int i=1; i<=n; i++) { store[c[i-1]].push_back(i); for (int x:a[i]) { for (int y:store[x]) d[y]=i; store[x].clear(); } } for (int i=1; i<=n; i++) store[i].clear(); for (int i=n; i>=1; i--) { store[c[i]].push_back(i); for (int x:a[i]) { for (int y:store[x]) e[y]=i; store[x].clear(); } } cin >> q; for (int i=1; i<=q; i++) cin >> X[i] >> Y[i]; for (int i=1; i<=n; i++) { event.push_back({{e[i]+1, 0}, {0, i}}); event.push_back({{i, 0}, {1, d[i]-1}}); } for (int i=1; i<=q; i++) if (X[i]<Y[i]) event.push_back({{X[i], i}, {X[i], Y[i]-1}}); solve(0); event.clear(); for (int i=1; i<=n; i++) { event.push_back({{n-d[i]+2, 0}, {0, i}}); event.push_back({{n-i+1, 0}, {1, e[i]+1}}); } for (int i=1; i<=q; i++) if (X[i]>Y[i]) event.push_back({{n-X[i]+1, i}, {Y[i]+1, X[i]}}); solve(1); for (int i=1; i<=q; i++) cout << (ans[i]?"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...