#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
struct segtree{
int sz; vi mx; vi a;
void build(int v, int tl, int tr){
if (tl==tr) {mx[v]=tl; return;}
int tm=(tl+tr)/2;
build(2*v,tl,tm); build(2*v+1,tm+1,tr);
if (a[mx[2*v]] >= a[mx[2*v+1]]) mx[v]=mx[2*v];
else mx[v]=mx[2*v+1];
}
void init(int n, vi A){
sz=n; mx.assign(4*n,-1); a=A; build(1,0,n-1);
}
void rem(int v, int tl, int tr, int pos){
if (tl==tr){mx[v]=-1; return;}
int tm=(tl+tr)/2;
if (pos<=tm) rem(2*v,tl,tm,pos);
else rem(2*v+1,tm+1,tr,pos);
if (mx[2*v] != -1 && mx[2*v+1] != -1){
if (a[mx[2*v]] >= a[mx[2*v+1]]) mx[v]=mx[2*v];
else mx[v]=mx[2*v+1];
}else{
if (mx[2*v]==-1) mx[v]=mx[2*v+1];
else mx[v]=mx[2*v];
}
}
void rem(int pos){rem(1,0,sz-1,pos);}
int qry(int v, int tl, int tr, int l, int r){
if (tl==l && tr==r) return mx[v];
if (l>r) return -1;
int tm=(tl+tr)/2;
int L=qry(2*v,tl,tm,l,min(r,tm)), R=qry(2*v+1,tm+1,tr,max(l,tm+1),r);
if (L==-1) return R;
if (R==-1) return L;
if (a[L]>=a[R]) return L;
return R;
}
int qry(int l, int r){return qry(1,0,sz-1,l,r);}
};
void solve(){
int n; cin>>n;
vi l(n+1), r(n+1);
FOR(i,1,n+1) cin>>l[i]>>r[i];
FOR(i,1,n+1) l[i]=n-l[i];
segtree stl, str;
stl.init(n+1,l); str.init(n+1,r);
vi d1(n+1,n+2); queue<int> bfs;
d1[1]=0; stl.rem(1); str.rem(1);
FOR(i,2,n+1){
if (n-l[i]==1){ // l[i]==1 (l[i] was changed into n-l[i] in line 55)
stl.rem(i); str.rem(i); bfs.push(i); d1[i]=1;
}
}
while (!bfs.empty()){
int u = bfs.back(); bfs.pop();
int val = str.qry(1,u);
while (val != -1 && r[val] >= u){
stl.rem(val); str.rem(val); bfs.push(val); d1[val]=d1[u]+1;
//cout<<u<<" "<<d1[u]<<" "<<val<<" "<<d1[val]<<"\n";
val=str.qry(1,u);
}
val = stl.qry(u,n);
while (val!=-1 && l[val] >= n-u){
stl.rem(val); str.rem(val); bfs.push(val); d1[val]=d1[u]+1;
//cout<<u<<" "<<d1[u]<<" "<<val<<" "<<d1[val]<<"\n";
val=stl.qry(u,n);
}
}
//FOR(i,1,n+1) cout<<d1[i]<<" "; cout<<"\n";
vi dn(n+1,n+2);
stl.init(n+1,l); str.init(n+1,r);
dn[n]=0; stl.rem(n); str.rem(n);
FOR(i,1,n){
if (r[i]==n){
stl.rem(i); str.rem(i); bfs.push(i); dn[i]=1;
}
}
while (!bfs.empty()){
int u = bfs.back(); bfs.pop();
int val = str.qry(1,u);
while (val != -1 && r[val] >= u){
stl.rem(val); str.rem(val); bfs.push(val); dn[val]=dn[u]+1;
val=str.qry(1,u);
}
val = stl.qry(u,n);
while (val!=-1 && l[val] >= n-u){
stl.rem(val); str.rem(val); bfs.push(val); dn[val]=dn[u]+1;
val=stl.qry(u,n);
}
}
//FOR(i,1,n+1) cout<<dn[i]<<" "; cout<<"\n";
vi ans(n+1); FOR(i,1,n+1) ans[i]=d1[i]+dn[i]-1; ans[1]++; ans[n]++;
int mn=ans[1]; FOR(i,2,n+1) mn=min(mn,ans[1]);
stl.init(n+1,l); str.init(n+1,r);
priority_queue<ii,vii,greater<ii>> pq;
FOR(i,1,n+1){
if (ans[i]<=n) pq.push({ans[i],i});
}
while (!pq.empty()){
ii node = pq.top(); pq.pop();
int u = node.se;
if (ans[u] != node.fi) continue;
int val = str.qry(1,u);
while (val != -1 && r[val] >= u){
stl.rem(val); str.rem(val); bfs.push(val);
if (ans[val] > ans[u]+1){
ans[val]=ans[u]+1; pq.push({ans[val],val});
}
val=str.qry(1,u);
}
val = stl.qry(u,n);
while (val!=-1 && l[val] >= n-u){
stl.rem(val); str.rem(val); bfs.push(val);
if (ans[val] > ans[u]+1){
ans[val]=ans[u]+1; pq.push({ans[val],val});
}
val=stl.qry(u,n);
}
}
cout<<dn[1]<<"\n"; return;
int q; cin>>q;
while(q--){
int x; cin>>x;
if (ans[x]>n) ans[x]=-1;
cout<<ans[x]<<"\n";
}
}
int main(){
//MOD=MOD1;
ios::sync_with_stdio(false);
if (fopen("input.txt", "r")) {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
}
int TC = 1;
//cin >> TC;
FOR(i, 1, TC+1){
//cout << "Case #" << i << ": ";
solve();
}
return 0;
}
Compilation message
passport.cpp: In function 'int main()':
passport.cpp:151:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
151 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:152:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
