#include<iostream>
#include<vector>
#include<utility>
#include<map>
using namespace std;
struct st{
vector<int> vec;
st(int n){
vec.resize(4 * n + 4);
}
void build(int l, int r, int ind, vector<int>& sr){
if(l == r){
vec[ind] = sr[l];
}
else{
int mid = (l + r) >> 1;
build(l, mid, ind * 2, sr);
build(mid + 1, r, ind * 2 + 1, sr);
vec[ind] = min(vec[ind * 2], vec[ind * 2 + 1]);
}
}
void modify(int l, int r, int num, int pos, int ind){
if(l == r){
vec[ind] = num;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) modify(l, mid, num, pos, ind * 2);
else modify(mid + 1, r, num, pos, ind * 2 + 1);
vec[ind] = min(vec[ind * 2], vec[ind * 2 + 1]);
}
int query(int l, int r, int start, int end, int ind){
if(r < start || end < l) return 1e9;
if(start <= l && r <= end) return vec[ind];
int mid = (l + r) >> 1;
return min(query(l, mid, start, end, ind * 2), query(mid + 1, r, start, end, ind * 2 + 1));
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<pair<int, int>> vec(n + 1);
for(int i = 1; i <= n; i++) cin >> vec[i].first >> vec[i].second;
map<pair<int, int>, vector<int>> m;
for(int i = 1; i <= n; i++){
m[vec[i]].push_back(i);
}
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 1e9));
dp[1][n] = 0;
st minl(n), maxr(n), mindp(n);
vector<int> tmp(n + 1);
for(int i = 1; i <= n; i++) tmp[i] = vec[i].first;
minl.build(1, n, 1, tmp);
for(int i = 1; i <= n; i++) tmp[i] = -vec[i].second;
maxr.build(1, n, 1, tmp);
for(int i = 1; i <= n; i++) tmp[i] = 1e9;
mindp.build(1, n, 1, tmp);
for(auto x: m[make_pair(1, n)]){
mindp.modify(1, n, dp[1][n], x, 1);
}
for(int l = n - 1; l > 0; l--){
for(int i = 1; i + l - 1 <= n; i++){
int j = i + l - 1;
dp[i][j] = min(dp[i][j], dp[minl.query(1, n, i, j, 1)][j] + 1);
dp[i][j] = min(dp[i][j], dp[i][-maxr.query(1, n, i, j, 1)] + 1);
dp[i][j] = min(dp[i][j], mindp.query(1, n, i, j, 1) + 1);
for(auto x: m[make_pair(i, j)]){
mindp.modify(1, n, dp[i][j], x, 1);
}
}
}
int q;
cin >> q;
while(q--){
int a;
cin >> a;
if(dp[a][a] == 1e9) cout << "-1\n";
else cout << dp[a][a] << "\n";
}
}
// g++ -std=gnu++20 pC.cpp -o run -Wall -Wextra -fsanitize=undefined -fsanitize=address
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
461 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
19 ms |
3852 KB |
Output is correct |
| 12 |
Correct |
19 ms |
4072 KB |
Output is correct |
| 13 |
Correct |
20 ms |
4188 KB |
Output is correct |
| 14 |
Correct |
19 ms |
3908 KB |
Output is correct |
| 15 |
Correct |
19 ms |
4188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
19 ms |
3852 KB |
Output is correct |
| 12 |
Correct |
19 ms |
4072 KB |
Output is correct |
| 13 |
Correct |
20 ms |
4188 KB |
Output is correct |
| 14 |
Correct |
19 ms |
3908 KB |
Output is correct |
| 15 |
Correct |
19 ms |
4188 KB |
Output is correct |
| 16 |
Execution timed out |
2068 ms |
232316 KB |
Time limit exceeded |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
19 ms |
3852 KB |
Output is correct |
| 12 |
Correct |
19 ms |
4072 KB |
Output is correct |
| 13 |
Correct |
20 ms |
4188 KB |
Output is correct |
| 14 |
Correct |
19 ms |
3908 KB |
Output is correct |
| 15 |
Correct |
19 ms |
4188 KB |
Output is correct |
| 16 |
Execution timed out |
2068 ms |
232316 KB |
Time limit exceeded |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
461 ms |
1048576 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
