Submission #1261697

#TimeUsernameProblemLanguageResultExecution timeMemory
1261697ereringPassport (JOI23_passport)C++20
40 / 100
2095 ms6472 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define pb push_back const int N=2e5+5,inf=1e18; int n; pair<int,int> p[N]; int seg[N*4],offset=1; void update(int idx,int val){ idx+=offset; seg[idx]=val; idx/=2; while(idx>0){ seg[idx]=max(seg[idx*2],seg[idx*2+1]); idx/=2; } } int query(int node,int qlo,int qhi,int lo,int hi){ if(lo>=qlo && hi<=qhi)return seg[node]; if(lo>qhi || hi<qlo)return 0; int mid=(lo+hi)/2; return max(query(node*2,qlo,qhi,lo,mid),query(node*2+1,qlo,qhi,mid+1,hi)); } int solve(int l,int r){ for(int i=1;i<=n;i++)update(i,0); queue<pair<int,pair<int,int>>> bfs; bfs.push({1,{l,r}}); update(l,r); while(!bfs.empty()){ int score=bfs.front().first; l=bfs.front().second.first; r=bfs.front().second.second; bfs.pop(); if(l==1 && r==n)return score; for(int i=l;i<=r;i++){ if(l<=p[i].first && r>=p[i].second)continue; int nl=min(l,p[i].first),nr=max(r,p[i].second); if(query(1,1,nl,0,offset-1)>=nr)continue; update(nl,nr); bfs.push({score+1,{nl,nr}}); } } return -1; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; while(offset<=n)offset*=2; for(int i=1;i<=n;i++)cin>>p[i].first>>p[i].second; int q; cin>>q; while(q--){ int x; cin>>x; cout<<solve(p[x].first,p[x].second)<<endl; } }
#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...