Submission #1182742

#TimeUsernameProblemLanguageResultExecution timeMemory
1182742PieArmyRailway Trip 2 (JOI22_ho_t4)C++20
36 / 100
762 ms54668 KiB
#include<bits/stdc++.h> typedef long long ll; #define pb push_back #define fr first #define sc second using namespace std; int n,k,m; int lefs[100023],rigs[100023]; vector<int>leftmost[100023],rightmost[100023]; pair<int,int>tree[400023][18]; void it(){ multiset<int>stl,str; for(int i=1;i<=n;i++){ for(int x:rightmost[i]){ if(x<0)str.erase(str.find(x)); else str.insert(-x); } for(int x:leftmost[i]){ if(x<0)stl.erase(stl.find(-x)); else stl.insert(x); } if(str.size()){ rigs[i]=max(rigs[i],-*str.begin()); } if(stl.size()){ lefs[i]=min(lefs[i],*stl.begin()); } } } void build(int lg,int node=1,int left=1,int right=-1){ if(right==-1)right=n; if(left==right){ tree[node][lg].fr=lefs[left]; tree[node][lg].sc=rigs[left]; return; } const int mid=(left+right)>>1; build(lg,node*2,left,mid); build(lg,node*2+1,mid+1,right); tree[node][lg]={min(tree[node*2][lg].fr,tree[node*2+1][lg].fr),max(tree[node*2][lg].sc,tree[node*2+1][lg].sc)}; } pair<int,int> query(int lg,int l,int r,int node=1,int left=1,int right=-1){ if(right==-1)right=n; if(left>r||right<l)return {n+1,-n-1}; if(left>=l&&right<=r)return tree[node][lg]; const int mid=(left+right)>>1; pair<int,int>res1=query(lg,l,r,node*2,left,mid),res2=query(lg,l,r,node*2+1,mid+1,right); return {min(res1.fr,res2.fr),max(res1.sc,res2.sc)}; } int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); cin>>n>>k>>m; for(int i=1;i<=n;i++){ lefs[i]=i; rigs[i]=i; } for(int i=1;i<=m;i++){ int a,b;cin>>a>>b; if(a<b){ rightmost[a].pb(b); rightmost[min(a+k-1,b)+1].pb(-b); } else{ leftmost[max(a-k+1,b)].pb(b); leftmost[a+1].pb(-b); } } it(); build(0); for(int i=1;i<18;i++){ for(int j=1;j<=n;j++){ //cout<<lefs[j]<<":"<<rigs[j]<<" "; pair<int,int>p=query(i-1,lefs[j],rigs[j]); lefs[j]=p.fr; rigs[j]=p.sc; } //cout<<endl; build(i); } int q;cin>>q; while(q--){ int s,t;cin>>s>>t; int l=s,r=s; int ans=1; for(int i=18-1;i>=0;i--){ pair<int,int>p=query(i,l,r); if(t>=p.fr&&t<=p.sc)continue; ans+=(1<<i); l=p.fr; r=p.sc; } if(ans>=m){ cout<<-1; } else cout<<ans; cout<<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...
#Verdict Execution timeMemoryGrader output
Fetching results...