제출 #704423

#제출 시각아이디문제언어결과실행 시간메모리
704423ld_minh4354Railway Trip 2 (JOI22_ho_t4)C++17
27 / 100
2066 ms31472 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pb push_back #define debug(x) cout<<#x<<": "<<x<<"\n" struct node { int s,e,m,val,lazy; node *l,*r; node(int S,int E) { s=S;e=E;m=(s+e)/2; val=S;lazy=1e9; if (s!=e) { l=new node(s,m); r=new node(m+1,e); } } void prop() { if (lazy==1e9) return; val=min(val,lazy); if (s!=e) { l->lazy = min(l->lazy,lazy); r->lazy = min(r->lazy,lazy); } lazy=1e9; } void update(int S,int E,int V) { if (s==S and e==E) lazy = min(lazy, V); else { if (E<=m) l->update(S,E,V); else if (S>m) r->update(S,E,V); else { l->update(S,m,V);r->update(m+1,E,V); } l->prop();r->prop(); val=min(l->val,r->val); } } int query(int S,int E) { prop(); if (s==S and e==E) return val; else if (E<=m) return l->query(S,E); else if (S>m) return r->query(S,E); else return min(l->query(S,m), r->query(m+1,E)); } }*lroot; struct node2 { int s,e,m,val,lazy; node2 *l,*r; node2(int S,int E) { s=S;e=E;m=(s+e)/2; val=E;lazy=0; if (s!=e) { l=new node2(s,m); r=new node2(m+1,e); } } void prop() { if (lazy==0) return; val=max(val,lazy); if (s!=e) { l->lazy = max(l->lazy,lazy); r->lazy = max(r->lazy,lazy); } lazy=0; } void update(int S,int E,int V) { if (s==S and e==E) lazy = max(lazy, V); else { if (E<=m) l->update(S,E,V); else if (S>m) r->update(S,E,V); else { l->update(S,m,V);r->update(m+1,E,V); } l->prop();r->prop(); val=max(l->val,r->val); } } int query(int S,int E) { prop(); if (s==S and e==E) return val; else if (E<=m) return l->query(S,E); else if (S>m) return r->query(S,E); else return max(l->query(S,m), r->query(m+1,E)); } }*rroot; signed main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); // freopen("input.000","r",stdin); // freopen("output.000","w",stdout); // srand((unsigned)time(NULL)); // rand() int n,k,m,a[200005],b[200005],s,t,l,lnew,r,rnew,ans,i,q; bool stop; cin>>n>>k>>m; for (i=1;i<m+1;i++) cin>>a[i]>>b[i]; lroot=new node(1,n); rroot=new node2(1,n); for (i=1;i<m+1;i++) if (a[i]<b[i]) rroot->update(a[i], min(a[i]+k-1,b[i]), b[i]); else lroot->update(max(a[i]-k+1,b[i]), a[i], b[i]); cin>>q; for (i=1;i<q+1;i++) { cin>>s>>t; ans=0;l=r=s;stop=false; while ((t<l or t>r) and !stop) { lnew=lroot->query(l,r); rnew=rroot->query(l,r); if (l==lnew and r==rnew) stop=true; l=lnew;r=rnew;ans++; } if (stop) cout<<"-1\n";else cout<<ans<<"\n"; } }
#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...