이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#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=21;
int lg[N];
vector<int>addR[N];
vector<int>addL[N];
int l[N],r[N];
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;
pair<int,int>up[Lg][N];
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();
for (int i=1;i<=n;i++){
up[0][i]={L.get(l[i],r[i]),R.get(l[i],r[i])};
}
for (int j=1;j<=Lg;j++){
for (int i=1;i<=n;i++){
///calc up[j][i]
vector<int>consider;
consider.push_back(up[j-1][up[j-1][i].first].first);
consider.push_back(up[j-1][up[j-1][i].first].second);
consider.push_back(up[j-1][up[j-1][i].second].first);
consider.push_back(up[j-1][up[j-1][i].second].second);
up[j][i]=up[j-1][i];
for (int x:consider){
if (l[x]<l[up[j][i].first]) up[j][i].first=x;
if (r[x]>r[up[j][i].second]) up[j][i].second=x;
}
}
}
int q;cin>>q;
for (int i=1;i<=q;i++){
int s,t;cin>>s>>t;
if (l[up[Lg-1][s].first]>t || r[up[Lg-1][s].second]<t){
cout<<-1<<'\n';
continue;
}
if (l[s]<=t && t<=r[s]){
cout<<1<<'\n';
continue;
}
int res=0;
int sL=s,sR=s;
for (int j=Lg-1;j>=0;j--){
int nwL=sL;
int nwR=sR;
vector<int>consider;
consider.push_back(up[j][sL].first);
consider.push_back(up[j][sL].second);
consider.push_back(up[j][sR].first);
consider.push_back(up[j][sR].second);
for (int x:consider){
if (l[x]<l[nwL]) nwL=x;
if (r[x]>r[nwR]) nwR=x;
}
if (l[nwL]>t || r[nwR]<t){
res+=(1<<j);
sL=nwL;
sR=nwR;
}
}
res+=2;
cout<<res<<'\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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |