#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int INF = 1e18;
const int N = 2505;
vector<array<int,3>> v[N][N];
void _(){
int n;
cin >> n;
int L[n],R[n];
for(int i = 0; i < n; i++){
cin >> L[i] >> R[i];
--L[i], --R[i];
}
vector<vector<int>> dist(n, vector<int>(n, INF));
for(int i = 0; i < n; i++){
int left = -1, right = -1;
for(int j = i; j < n; j++){
if(left == -1 || L[j] < L[left]) left = j;
if(right == -1 || R[j] > R[right]) right = j;
v[L[left]][j].push_back({i, j, 1});
v[i][R[right]].push_back({i, j, 1});
if(i == j){
v[L[i]][R[i]].push_back({i, i, 1});
}
if(i < j){
v[i + 1][j].push_back({i, j, 0});
v[i][j - 1].push_back({i, j, 0});
}
}
}
dist[0][n-1] = 0;
deque<array<int,2>> dq;
dq.push_back({0, n - 1});
while(!dq.empty()){
int l = dq.front()[0], r = dq.front()[1];
dq.pop_front();
for(auto [x, y, w] : v[l][r]){
if(w == 0 && dist[l][r] < dist[x][y]){
dist[x][y] = dist[l][r];
dq.push_front({x, y});
}
else if(w == 1 && dist[l][r] + 1 < dist[x][y]){
dist[x][y] = dist[l][r] + 1;
dq.push_back({x, y});
}
}
}
int q;
cin >> q;
while(q--){
int c; cin >> c;
--c;
if(dist[c][c] == INF) cout << -1 << '\n';
else cout << dist[c][c] << '\n';
}
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |