#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int fl[maxn],fr[maxn],dpl[maxn],kaf=(1<<18),dpr[maxn],dp[maxn],inf=1e8,n;
pair<int,int>all[maxn];
vector<int>adj[maxn];
struct segment{
pair<int,int>seg[(1<<19)];
segment(){
for(int i=0;i<(1<<19);i++){
seg[i]=make_pair(-inf,-inf);
}
}
void clear(){
for(int i=0;i<(1<<19);i++){
seg[i]=make_pair(-inf,-inf);
}
}
void ins(int i,pair<int,int>w){
i+=kaf;
seg[i]=w;
i>>=1;
while(i>0){
seg[i]=max(seg[(i<<1)],seg[(i<<1)^1]);
i>>=1;
}
}
pair<int,int> pors(int i,int l,int r,int tl,int tr){
if(l>r||l>tr||r<tl||tl>tr){
return make_pair(-inf,-inf);
}
if(l>=tl&&r<=tr){
return seg[i];
}
int m=(l+r)>>1;
return max(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
}
}seg;
void vorod(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>all[i].first>>all[i].second;
}
}
void calfr(int ind){
fr[ind]=seg.pors(1,0,kaf-1,all[ind].first,all[ind].second).second;
if(all[fr[ind]].second==all[ind].second){
fr[ind]=-1;
}else{
adj[fr[ind]].push_back(ind);
}
}
void calr(){
seg.clear();
for(int i=1;i<=n;i++){
seg.ins(i,make_pair(all[i].second,i));
}
for(int i=1;i<=n;i++){
dpr[i]=inf;
calfr(i);
}
vector<pair<int,int>>v;
for(int i=1;i<=n;i++){
v.push_back(make_pair(all[i].second,i));
}
sort(v.rbegin(),v.rend());
for(int i=0;i<n;i++){
int u=v[i].second;
if(v[i].first==n){
dpr[u]=0;
continue;
}
if(fr[u]==-1){
continue;
}
dpr[u]=dpr[fr[u]]+1;
}
}
void calfl(int ind){
fl[ind]=seg.pors(1,0,kaf-1,all[ind].first,all[ind].second).second;
if(all[fl[ind]].first==all[ind].first){
fl[ind]=-1;
}else{
adj[fl[ind]].push_back(ind);
}
}
void call(){
seg.clear();
for(int i=1;i<=n;i++){
seg.ins(i,make_pair(-all[i].first,-i));
}
for(int i=1;i<=n;i++){
calfl(i);
dpl[i]=inf;
}
vector<pair<int,int>>v;
for(int i=1;i<=n;i++){
v.push_back(make_pair(all[i].first,i));
}
sort(v.begin(),v.end());
for(int i=0;i<n;i++){
int u=v[i].second;
if(v[i].first==1){
dpl[u]=0;
continue;
}
if(fl[u]==-1){
continue;
}
dpl[u]=dpl[fl[u]]+1;
}
}
void calres(){
set<pair<int,int>>st;
vector<int>vis(n+2);
for(int i=1;i<=n;i++){
dp[i]=dpr[i]+dpl[i]+1;
st.insert(make_pair(dp[i],i));
}
while((int)st.size()>0){
auto x=*st.begin();
st.erase(x);
if(vis[x.second]==1){
continue;
}
vis[x.second]=1;
dp[x.second]=x.first;
for(auto y:adj[x.second]){
st.insert(make_pair(x.first+1,y));
}
}
vector<pair<int,int>>v;
for(int i=1;i<=n;i++){
v.push_back(make_pair(all[i].second-all[i].first+1,i));
}
sort(v.rbegin(),v.rend());
for(int i=0;i<n;i++){
int u=v[i].second;
for(int j=all[u].first;j<=all[u].second;j++){
dp[u]=min(dp[u],dp[j]+(j!=u));
}
}
}
void pre(){
call();
calr();
calres();
}
void khor(){
int q;
cin>>q;
for(int i=1;i<=q;i++){
int x;
cin>>x;
if(dp[x]>=inf){
cout<<-1<<"\n";
}else{
cout<<dp[x]<<"\n";
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("inp.txt","r",stdin);
vorod();
pre();
khor();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
21596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
21500 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
21500 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
21500 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
21596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
