#include <bits/stdc++.h>
using namespace std;/*
<<<<It's never too late for a new beginning in your life>>>>
Today is hard
tomorrow will worse
but the day after tomorrow will be the sunshine..
HARD WORK BEATS TALENT WHEN TALENT DOESN'T WORK HARD............
Never give up */
//The most CHALISHKANCHIK
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vii;
const int N = 2e5+50;
int n;
pii stmn[20][N];
pii stmx[20][N];
pii getmn(int l, int r) {
int cl = __lg(r - l + 1);
if(min(stmn[cl][l].ff, stmn[cl][r - (1 << cl) + 1].ff) == stmn[cl][l].ff)return stmn[cl][l];
return stmn[cl][r - (1 << cl) + 1];
}
pii getmx(int l, int r) {
int cl = __lg(r - l + 1);
if(max(stmx[cl][l].ff, stmx[cl][r - (1 << cl) + 1].ff) == stmx[cl][l].ff)return stmx[cl][l];
return stmx[cl][r - (1 << cl) + 1];
}
void solve(){
int n;
cin >> n;
vii a(n);
for(int i = 1; i <= n; i++){
int l, r;
cin >> l >> r;
a[i] = {l, r};
stmn[0][i] = {l, i};
stmx[0][i] = {r, i};
}
for (int i = 1; i <= __lg(n); i++) {
int len = 1 << (i - 1);
for (int j = 1; j <= n; j++) {
stmn[i][j] = stmn[i - 1][j];
if(stmn[i][j].ff > stmn[i-1][min(j+len, n)].ff) stmn[i][j] = stmn[i - 1][ min(j + len, n) ];
if(stmn[i][j].ff == stmn[i-1][min(j+len, n)].ff){
if(a[stmn[i][j].ss].ss < a[stmn[i-1][min(j+len, n)].ss].ss)stmn[i][j] = stmn[i-1][min(j+len, n)];
}
}
}
for (int i = 1; i <= __lg(n); i++) {
int len = 1 << (i - 1);
for (int j = 1; j <= n; j++) {
stmx[i][j] = stmx[i - 1][j];
if(stmx[i][j].ff < stmx[i-1][min(j+len, n)].ff) stmx[i][j] = stmx[i - 1][ min(j + len, n) ];
if(stmx[i][j].ff == stmx[i-1][min(j+len, n)].ff){
if(a[stmx[i][j].ss].ff > a[stmx[i-1][min(j+len, n)].ss].ff)stmx[i][j] = stmx[i-1][min(j+len, n)];
}
}
}
int q;
cin >> q;
while(q--){
int ans = -1;
int x;
cin >> x;
priority_queue<pair<int,pii> > q;
q.push({1, a[x]});
while(!q.empty()){
auto [cnt, tu] = q.top();
q.pop();
int l = tu.ff,r = tu.ss;
if(l == 1 && r == n){
ans = cnt;
while(!q.empty())q.pop();
break;
}
pii fr = getmn(l, r);
int _l = min(l, fr.ff), _r = max(r, a[fr.ss].ss);
if(l!=_l||r!=_r)q.push({cnt+1, {_l, _r}});
pii sc = getmx(l, r);
_l = min(l, a[sc.ss].ff), _r = max(r, sc.ff);
if(l!=_l||r!=_r)q.push({cnt+1, {_l, _r}});
}
cout << ans << '\n';
}
}
main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t = 1;
//~ cin >> t;
while(t--){
solve();
}
}
Compilation message
passport.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
93 | main(){
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
12 ms |
21336 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
11 ms |
21340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
11 ms |
21340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
11 ms |
21340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
12 ms |
21336 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
