#include <bits/stdc++.h>
using namespace std;
// 0| 1| 2| 3| 4| 6|
// 23 1 1 3 4
vector<int> solve(int n, vector<int> walls, vector<vector<int> > keys){
// keys range from 0 to n+1
// rooms 0 ... n+1
// rooms
// 0 1 2 ... n n+1
// 0| 1| 2| n-1| n|
// walls
// for rooms 1 ... n, returns leftmost reachable room
vector<vector<int> > keylocations(n+2);
for(int i = 0; i <= n+1; i++){
for(int a : keys[i]){
keylocations[a].push_back(i);
}
}
vector<int> prevkey(n+1);
vector<int> nextkey(n+1);
for(int i = 0; i <= n; i++){
int type = walls[i];
auto it = lower_bound(keylocations[type].begin(), keylocations[type].end(), i+1);
nextkey[i] = *it;
prevkey[i] = *(it-1);
}
// for each wall, find farthest one so that there's a conflict
// then for a starting room, find dist to closest so that there is a conflict that extends past it
vector<int> conflict(n+1, -1);
for(int j = 0; j <= n; j++){
for(int k = n; k >= j; k--){
if(prevkey[k] <= j && nextkey[j] >= k+1){
conflict[j] = k;
break;
}
}
}
vector<int> ans(n+2, -1);
for(int j = 1; j <= n; j++){
for(int k = j-1; k >= 0; k--){
if(conflict[k] >= j){
ans[j] = j-1-k;
break;
}
}
assert(ans[j] != -1);
}
return ans;
}
int main(){
cin.sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
vector<int> walls; // what key need
walls.push_back(0);
for(int i = 1; i < n; i++){
int a;
cin >> a;
walls.push_back(a);
}
walls.push_back(n+1);
vector<vector<int> > keys(n+2);
for(int i = 0; i <= n+1; i++){
keys[0].push_back(i);
keys[n+1].push_back(i);
}
for(int i = 1; i <= n; i++){
int b;
cin >> b;
keys[i].resize(b);
for(int j = 0; j < b; j++){
cin >> keys[i][j];
}
}
int q;
cin >> q;
vector<int> x(q);
vector<int> y(q);
for(int i = 0; i < n; i++){
cin >> x[i] >> y[i];
}
vector<int> leftans = solve(n, walls, keys);
reverse(walls.begin(), walls.end());
reverse(keys.begin(), keys.end());
vector<int> rightans = solve(n, walls, keys);
reverse(rightans.begin(), rightans.end());
for(int i = 0; i < q; i++){
if(y[i]-x[i] <= rightans[x[i]] && y[i]-x[i] >= -leftans[x[i]]){
cout << "YES" << '\n';
} else {
cout << "NO" << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3038 ms |
30392 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
