Submission #1264122

#TimeUsernameProblemLanguageResultExecution timeMemory
1264122nguyenhuythachLong Mansion (JOI17_long_mansion)C++20
10 / 100
3096 ms33752 KiB
#include<bits/stdc++.h> #include<algorithm> #include<random> #include<chrono> #include<cstdlib> #include<ctime> #include<numeric> #include<vector> #include<stack> #include<map> #include<set> #include<queue> #include<iomanip> #define int long long #define ll long long #define fi first #define se second #define pii pair<int,int> #define sz(a) ((int)a.size()) #define FOR(i,j,k) for(int i=j;i<=k;i++) #define REP(i,k,j) for(int i=k;i>=j;i--) #define FORD(i,a) for(auto i:a) using namespace std; const int NMAX = 500000 + 5; int n,q; int c[NMAX]; vector<int> a[NMAX]; vector<int> pos[NMAX]; int lef[NMAX], rig[NMAX]; bool inside(int l, int r, int key) { if (key <= 0 || key >= NMAX) return false; auto &v = pos[key]; if (v.empty()) return false; auto it = lower_bound(v.begin(), v.end(), l); return it!=v.end() && *it <= r; } void input() { ios::sync_with_stdio(false); cin.tie(nullptr); if(!(cin>>n)) exit(0); FOR(i,1,n-1) cin>>c[i]; FOR(i,1,n) { int b; cin>>b; a[i].resize(b); FOR(j,0,b-1) { cin>>a[i][j]; if (a[i][j] >= 0 && a[i][j] < NMAX) pos[a[i][j]].push_back(i); } } cin>>q; } void solve() { FOR(i,1,n) { lef[i]=rig[i]=i; bool nxt = true; while(nxt) { nxt = false; while (lef[i] > 1 && inside(lef[i], rig[i], c[lef[i]-1]) ) { int L = lef[lef[i]-1]; int R = rig[lef[i]-1]; lef[i] = L; if (R > rig[i]) rig[i] = R; nxt = true; } while (rig[i] < n && inside(lef[i], rig[i], c[rig[i]])) { rig[i]++; if (rig[i] < i) { if (lef[rig[i]] < lef[i]) lef[i] = lef[rig[i]]; if (rig[rig[i]] > rig[i]) rig[i] = rig[rig[i]]; } nxt = true; } } } while(q--) { int x,y; cin>>x>>y; if (x<=y) { if (lef[x] <= y && y <= rig[x]) cout<<"YES\n"; else cout<<"NO\n"; }else { if (lef[x] <= y && y <= rig[x]) cout<<"YES\n"; else cout<<"NO\n"; } } } signed main() { input(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...