#include <bits/stdc++.h>
#define getbit(i, j) ((i >> j) & 1)
#define maxn 200005
#define name "Passport"
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long GetRandom(long long l, long long r)
{
return uniform_int_distribution<long long> (l, r)(rng);
}
int n,q,r[maxn];
int dpl[2505][2505],dpr[2505][2505];
pair<int,int> a[maxn];
int f[2505][2505],xd[2505][2505];
int tinh(int d,int c)
{
if(d>c) return 1e9;
if(d==1&&c==n) return 0;
if(xd[d][c]==1) return f[d][c];
xd[d][c]=1;
int val=1e9;
int u=dpl[d][c];
val=min(val,tinh(u,c)+1);
u=dpr[d][c];
val=min(val,tinh(d,u)+1);
val=min({val,tinh(d+1,c),tinh(d,c-1)});
if(d==c) val=min(val,tinh(a[d].first,a[d].second)+1);
f[d][c]=val;
return f[d][c];
}
void sub1()
{
int vt=1,sl=0;
while(vt<n)
{
int luu=vt;
// cout<<vt<<' '<<dpr[1][vt]<<'\n';
vt=r[vt];
sl++;
if(luu==vt) break;
}
if(vt!=n) cout<<-1<<'\n';
else cout<<sl<<'\n';
exit(0);
}
void sub3()
{
for(int i=1;i<=n;i++)
{
dpl[i][i]=a[i].first;
dpr[i][i]=a[i].second;
for(int j=i+1;j<=n;j++)
{
dpl[i][j]=min(dpl[i][j-1],a[j].first);
dpr[i][j]=max(dpr[i][j-1],a[j].second);
}
}
r[1]=a[i].second;
for(int i=2;i<=n;i++) r[i]=max(r[i-1],a[i].second);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) f[i][j]=1e9;
}
for(int i=1;i<=q;i++)
{
int x;
cin >> x;
if(q==1&&x==1) sub1();
int val=tinh(x,x);
if(val>n) cout<<-1<<'\n';
else cout<<val<<'\n';
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
if(fopen(name".inp","r"))
{
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i].first >> a[i].second;
}
cin >> q;
if(n<=2500)sub3();
}
Compilation message
passport.cpp: In function 'void sub3()':
passport.cpp:66:12: error: 'i' was not declared in this scope
66 | r[1]=a[i].second;
| ^
passport.cpp: In function 'int main()':
passport.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
passport.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | freopen(name".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
