Submission #1264125

#TimeUsernameProblemLanguageResultExecution timeMemory
1264125nguyenhuythachLong Mansion (JOI17_long_mansion)C++20
100 / 100
243 ms67492 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 L LLONG_MAX #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> arr[NMAX]; vector<int> pos[NMAX]; int lef[NMAX], rig[NMAX]; int X[NMAX], Y[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; arr[i].resize(b); FOR(j,0,b-1) { cin >> arr[i][j]; if (arr[i][j] > 0 && arr[i][j] < NMAX) pos[ arr[i][j] ].push_back(i); } } cin >> q; FOR(i,1,q) cin >> X[i] >> Y[i]; } void solve() { FOR(i,1,n) { lef[i] = rig[i] = i; bool nxt = true; while (nxt) { nxt = false; if (lef[i] > 1 && inside(lef[i], rig[i], c[lef[i]-1])) { rig[i] = max(rig[i], rig[lef[i]-1]); lef[i] = lef[lef[i]-1]; nxt = true; continue; } if (rig[i] < n && inside(lef[i], rig[i], c[rig[i]])) { rig[i]++; nxt = true; } } } FOR(i,1,q) { int x = X[i], y = Y[i]; bool ok = (lef[x] <= y && y <= rig[x]); cout << (ok ? "YES" : "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...