제출 #593762

#제출 시각아이디문제언어결과실행 시간메모리
593762oleh1421Railway Trip 2 (JOI22_ho_t4)C++17
27 / 100
2071 ms38248 KiB
//#pragma GCC optimize("O3") //#pragma GCC target("avx2") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> //#define y2 y_2 //#define endl '\n' using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; const ll inf=1e18; mt19937 rnd(time(NULL)); const ll mod=998244353; const int N=200010; const int Lg=20; int lg[N]; vector<int>addR[N]; vector<int>addL[N]; int l[N],r[N]; pair<int,int>up[N][Lg]; struct SparseTable{ int mult; int a[N]; int best[Lg][N]; int n; void build(){ for (int i=1;i<=n;i++) a[i]*=mult; for (int i=1;i<=n;i++) best[0][i]=i; for (int j=1;j<Lg;j++){ for (int i=1;i<=n-(1<<j)+1;i++){ int x=best[j-1][i]; int y=best[j-1][i+(1<<(j-1))]; if (a[x]>a[y]) best[j][i]=x; else best[j][i]=y; } } } int get(int l,int r){ int len=lg[r-l+1]; int x=best[len][l]; int y=best[len][r-(1<<len)+1]; // if (l+(1<<len)-1>n) exit(1); if (a[x]>a[y]) return x; return y; } }; SparseTable L; SparseTable R; void solve(){ int n,k,m;cin>>n>>k>>m; for (int i=1;i<=m;i++){ int a,b;cin>>a>>b; if (a<b){ int l=a; int r=min(a+k-1,b-1); addR[l].push_back(b); addR[r+1].push_back(-b); } else { swap(a,b); int r=b; int l=max(a+1,b-k+1); addL[r].push_back(a); addL[l-1].push_back(-a); } } multiset<int>st; for (int i=1;i<=n;i++){ for (int x:addR[i]){ if (x<0) st.erase(st.find(-x)); else st.insert(x); } r[i]=i; if (!st.empty()) r[i]=max(r[i],(*st.rbegin())); } st.clear(); for (int i=n;i>=1;i--){ for (int x:addL[i]){ if (x<0) st.erase(st.find(-x)); if (x>0) st.insert(x); } l[i]=i; if (!st.empty()) l[i]=min(l[i],(*st.begin())); } L.mult=-1; R.mult=1; L.n=R.n=n; for (int i=1;i<=n;i++){ // cout<<i<<" "<<l[i]<<" "<<r[i]<<'\n'; L.a[i]=l[i]; R.a[i]=r[i]; } L.build(); R.build(); int q;cin>>q; for (int i=1;i<=q;i++){ int s,t;cin>>s>>t; int sL=s,sR=s; int res=0; while (t<sL || t>sR){ int nwL=l[L.get(sL,sR)]; int nwR=r[R.get(sL,sR)]; if (nwL==sL && nwR==sR) break; // cout<<sL<<" "<<sR<<" "<<nwL<<" "<<nwR<<" "<<L.get(sL,sR)<<endl; sL=nwL; sR=nwR; res++; } if (sL<=t && t<=sR) cout<<res<<'\n'; else cout<<-1<<'\n'; } } int32_t main() { lg[1]=0; for (int i=2;i<N;i++) lg[i]=lg[i/2]+1; ios_base::sync_with_stdio(false); cin.tie(0); int tt=1; // cin>>tt; while (tt--){ solve(); } return 0; } /** 3 5 2 7 3 1 6 8 4 **/
#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...