Submission #1217545

#TimeUsernameProblemLanguageResultExecution timeMemory
1217545noyancanturkPassport (JOI23_passport)C++20
6 / 100
272 ms42820 KiB
#include<bits/stdc++.h> using namespace std; #define int int64_t #define pb push_back using pii=pair<int,int>; const int lim=2e5+100; struct{ pii tree[4*lim]; void build(){ for(pii&p:tree)p={-1,0}; } int P,VAL; pii update(int l,int r,int node){ if(l==r)return tree[node]={VAL,l}; int mid=l+r>>1,child=node<<1; if(P<=mid)return tree[node]=max(update(l,mid,child),tree[child|1]); return tree[node]=max(tree[child],update(mid+1,r,child|1)); } pii query(int l,int r,int node){ if(r<=P)return tree[node]; int mid=l+r>>1,child=node<<1; if(P<=mid)return query(l,mid,child); return max(tree[child],query(mid+1,r,child|1)); } void update(int p,int val){ P=p,VAL=val; update(0,lim-1,1); } pii query(int p){ P=p; return query(0,lim-1,1); } }stmax; struct{ pii tree[4*lim]; void build(){ for(pii&p:tree)p={INT_MAX,0}; } int P,VAL; pii update(int l,int r,int node){ if(l==r)return tree[node]={VAL,l}; int mid=l+r>>1,child=node<<1; if(P<=mid)return tree[node]=min(update(l,mid,child),tree[child|1]); return tree[node]=min(tree[child],update(mid+1,r,child|1)); } pii query(int l,int r,int node){ if(P<=l)return tree[node]; int mid=l+r>>1,child=node<<1; if(mid+1<=P)return query(mid+1,r,child|1); return min(query(l,mid,child),tree[child|1]); } void update(int p,int val){ P=p,VAL=val; update(0,lim-1,1); } pii query(int p){ P=p; return query(0,lim-1,1); } }stmin; signed main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n,q; cin>>n; int a[n],b[n]; for(int i=0;i<n;i++){ cin>>a[i]>>b[i]; a[i]--,b[i]--; } cin>>q; int c[q]; for(int i=0;i<q;i++){ cin>>c[i]; c[i]--; } int costleft[n],costright[n]; vector<int>v; for(int i=0;i<n;i++){ if(a[i]==0){ costleft[i]=0; v.clear(); v.pb(i); }else{ auto p=lower_bound(v.begin(),v.end(),a[i]); if(p==v.end()){ costleft[i]=INT_MAX; }else{ costleft[i]=p-v.begin()+1; while(v.back()!=*p){ v.pop_back(); } v.pb(i); } } } v.clear(); for(int i=n-1;0<=i;i--){ if(b[i]==n-1){ costright[i]=0; v.clear(); v.pb(i); }else{ auto p=lower_bound(v.begin(),v.end(),b[i],greater<int>()); if(p==v.end()){ costright[i]=INT_MAX; }else{ costright[i]=p-v.begin()+1; while(v.back()!=*p){ v.pop_back(); } v.pb(i); } } } stmin.build(); stmax.build(); int cost[n]; for(int i=0;i<n;i++){ cost[i]=costleft[i]+costright[i]; stmin.update(i,a[i]); stmax.update(i,b[i]); } priority_queue<pii,vector<pii>,greater<pii>>pq; int vis[n]{}; for(int i=0;i<n;i++){ pq.push({cost[i],i}); } while(pq.size()){ auto[ds,node]=pq.top(); pq.pop(); if(vis[node])continue; while(node){ auto[mx,ind]=stmax.query(node-1); if(node<=mx){ stmax.update(ind,0); if(cost[node]+1<cost[ind]){ cost[ind]=cost[node]+1; pq.push({cost[ind],ind}); } }else break; } while(node<n-1){ auto[mn,ind]=stmin.query(node+1); if(mn<=node){ stmin.update(ind,n); if(cost[node]+1<cost[ind]){ cost[ind]=cost[node]+1; pq.push({cost[ind],ind}); } }else break; } } for(int i=0;i<n;i++){ if(cost[i]>n-1)cost[i]=-2; } for(int i=0;i<q;i++){ cout<<cost[c[i]]+1<<'\n'; } // for(int i=0;i<n;i++){ // cout<<'\n'<<cost[i]+1; // } }
#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...