Submission #953831

#TimeUsernameProblemLanguageResultExecution timeMemory
953831amirhoseinfar1385Passport (JOI23_passport)C++17
0 / 100
2090 ms17500 KiB
#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++){ 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(x!=1){ assert(0); } 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...