#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10;
int fl[maxn],fr[maxn],dpl[maxn],dpr[maxn],dp[maxn],inf=1e8,n;
pair<int,int>all[maxn];
vector<int>adj[maxn];
void vorod(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>all[i].first>>all[i].second;
}
}
void calfr(int ind){
int mx=all[ind].second;
fr[ind]=-1;
for(int i=all[ind].first;i<=all[ind].second;i++){
if(all[i].second>mx){
mx=all[i].second;
fr[ind]=i;
}
}
if(fr[ind]>0){
adj[fr[ind]].push_back(ind);
}
}
void calr(){
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){
int mn=all[ind].first;
fl[ind]=-1;
for(int i=all[ind].first;i<=all[ind].second;i++){
if(all[i].first<mn){
mn=all[i].first;
fl[ind]=i;
}
}
if(fl[ind]>0){
adj[fl[ind]].push_back(ind);
}
}
void call(){
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++){
// cout<<i<<" "<<fl[i]<<" "<<fr[i]<<" "<<dpl[i]<<" "<<dpr[i]<<endl;
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));
}
}
}
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();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 4 |
Execution timed out |
2083 ms |
9868 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 6 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 7 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 13 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 14 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 6 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 7 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 13 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 14 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 5 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 6 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 7 |
Correct |
1 ms |
8796 KB |
Output is correct |
| 8 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 9 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 10 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 11 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 12 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 13 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 14 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
8792 KB |
Output is correct |
| 2 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 3 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 4 |
Execution timed out |
2083 ms |
9868 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
