Submission #697097

#TimeUsernameProblemLanguageResultExecution timeMemory
697097amunduzbaevLong Mansion (JOI17_long_mansion)C++17
25 / 100
3077 ms52484 KiB
#include "bits/stdc++.h" using namespace std; #define ar array typedef long long ll; #define int ll const int N = 5e5 + 5; int c[N], b[N], last[N]; vector<int> a[N]; int l[N], r[N]; int L[N], R[N]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=1;i<n;i++){ cin >> c[i]; } for(int i=1;i<=n;i++){ cin >> b[i]; L[i] = 1, R[i] = n; a[i].resize(b[i]); for(int j=0;j<b[i];j++){ cin >> a[i][j]; } } for(int i=0;i<N;i++) last[i] = 0; for(int i=1;i<=n;i++){ for(auto x : a[i]){ last[x] = i; } l[i] = last[c[i]]; } for(int i=0;i<N;i++) last[i] = n + 1; for(int i=n;i>0;i--){ r[i] = last[c[i]]; for(auto x : a[i]){ last[x] = i; } } r[0] = N, l[n] = 0; for(int i=1;i<n;i++){ int j = r[i] - 1; for(;i < j;j--){ if(l[j] <= i){ break; } } if(i < j && l[j] <= i){ for(int k=i+1;k<=j;k++){ L[k] = max(L[k], i + 1); } } j = l[i]; for(;j < i;j++){ if(i < r[j]){ break; } } if(j < i && i < r[j]){ for(int k=j+1;k<=i;k++){ R[k] = min(R[k], i); } } } //~ for(int i=1;i<=n;i++){ //~ cout<<L[i]<<" "; //~ } cout<<"\n"; //~ for(int i=1;i<=n;i++){ //~ cout<<R[i]<<" "; //~ } cout<<"\n"; int q; cin >> q; while(q--){ int a, b; cin >> a >> b; if(L[a] <= b && b <= R[a]){ cout<<"YES\n"; } else { cout<<"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...