Submission #1188828

#TimeUsernameProblemLanguageResultExecution timeMemory
1188828yellowtoadLong Mansion (JOI17_long_mansion)C++20
0 / 100
3092 ms18620 KiB
#include <iostream> #include <vector> #define f first #define s second using namespace std; int n, m, test, a[500010], ll[500010], rr[500010], lst[500010]; vector<int> v[500010]; vector<pair<int,int>> rng; int main() { cin >> n; for (int i = 1; i < n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) { cin >> m; for (int j = 0; j < m; j++) { int x; cin >> x; v[i].push_back(x); } } for (int i = 1; i <= n; i++) lst[i] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < v[i].size(); j++) lst[v[i][j]] = i; if (i != n) ll[i] = lst[a[i]]; } ll[n] = 0; for (int i = 1; i <= n; i++) lst[i] = n+1; for (int i = n; i >= 1; i--) { if (i != n) rr[i] = lst[a[i]]; for (int j = 0; j < v[i].size(); j++) lst[v[i][j]] = i; } rr[0] = n+1; for (int i = 1; i <= n; i++) { for (int j = i-1; j >= ll[i]; j--) { if (rr[j] > i) { rng.push_back({j+1,i}); break; } } } cin >> test; while (test--) { int x, y; cin >> x >> y; for (int i = 0; i < rng.size(); i++) { if ((rng[i].f <= x) && (x <= rng[i].s)) { if (!((rng[i].f <= y) && (y <= rng[i].s))) { cout << "NO" << endl; goto skip; } } } cout << "YES" << endl; skip:; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...