#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)
using namespace std;
using namespace __gnu_pbds;
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡤⣴⠟⠋⢠⣴⣾⣿⡟⠋⠉⡳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠑⠒⠦⢤⣄⡀⠀⣴⡟⠋⡀⢠⣬⣿⣿⡿⠳⣄⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣫⡾⠋⠀⣶⣿⢿⣿⣥⠄⠠⠞⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⣌⣩⣿⡯⠁⣬⣭⣽⣿⣿⡟⠁⠈⠉⠝⢦⠀⠀
⠀⠀⠀⠀⠀⠀⠀⡼⣽⣟⡀⣠⣼⣿⣿⠟⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⣿⠃⠀⢠⣿⣿⣿⣿⡟⠀⠀⠀⠀⠀⠀⠱⣄
⠀⠀⠀⠀⠀⠀⠸⠃⠻⣿⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⣿⣧⣀⣼⠘⣿⠿⣸⠏⠀⣄⠀⠀⠀⠀⠀⠀⠈
⠀⠀⠀⠀⠀⠀⠇⠀⠀⠘⣿⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠻⣿⣿⣿⣿⣿⣿⣏⠀⠀⠈⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⠋⠀⠀⠀⠀⠀⠀⠀⢀⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣿⣿⣿⣿⣿⡝⠳⠀⢰⢱⡀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢀⡾⠁⠀⠀⠀⠀⠀⠀⠀⢠⣾⣇⠀⢸⠀⠀⠀⠀⠀⠀⠀⢱⢹⣷⠀⠀⠀⠀⠀⠰⡆⠉⠀⠀⠀⠀⠀⠀⢻⣿⣿⣿⣿⣷⡄⠀⠀⡏⡇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢠⠞⠀⢀⡔⠀⠀⠀⠀⠀⢀⣿⡿⢹⠀⢸⠀⠀⠀⠀⠀⡀⠀⠘⣿⡿⣷⠀⠀⠀⠀⠀⠹⡀⠀⢳⡀⠀⠀⠀⠀⢻⣿⣿⣿⣿⣿⡄⠀⢿⣻⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⡴⢣⡞⠀⠀⠀⠀⠀⢀⣾⡿⠁⢸⡇⢸⡇⠀⠀⠀⠀⣇⠀⠀⣿⠁⠙⣧⠀⠀⠀⠀⠀⢳⡀⠈⣇⠀⠀⠀⠀⠈⣿⣿⣿⣿⣿⣿⣆⢸⣟⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢀⡞⠀⠀⠀⠀⠀⠀⣼⡿⣁⣘⣀⢧⠈⣿⠀⠀⠀⠀⠸⡄⠀⣸⣀⣀⣹⣷⡀⠀⠀⠀⠀⢧⠀⢸⠀⠀⠀⠀⠀⢸⣿⣿⣿⣿⣿⡿⣿⣿⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⠀⠀⠀⠀⣰⡿⠋⡽⠉⠉⠘⡆⣿⣧⠀⠀⠀⠀⢧⠀⣿⣿⠉⠉⠙⣯⡑⠒⠀⠀⠘⣧⠘⡇⠀⠀⠀⠀⠀⢿⠐⠂⣩⠏⠀⣿⢿⡜⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢸⠃⠀⠀⠀⠀⠀⢰⣿⠃⣴⠁⠀⠀⠀⢻⣼⠹⡆⠀⠀⠀⢸⡇⣿⡟⠀⠀⠀⠈⢿⣄⠀⠀⠀⠙⡆⣷⠀⠀⠀⠀⠀⢸⣄⣠⣏⠀⢠⣿⡎⢧⣂⠀⠀⠀
⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⠀⠀⣾⠏⢠⣀⣀⣀⡠⠄⠀⢿⣧⠹⡄⠀⠀⠀⣿⣿⣣⠀⠳⣄⠀⠀⠹⣧⡀⠀⠀⢻⢻⠀⠀⠀⠀⠀⠀⣿⣷⣾⣷⡾⣿⡇⠸⣿⠀⠀⠀
⠀⠀⠀⠀⠀⢰⡇⠀⠀⠀⠀⠀⣸⣿⢀⣶⡿⠟⢛⣿⣷⣄⠈⣿⣆⠹⡄⠀⠀⢸⡇⣿⣀⣴⣾⠿⢿⣷⣮⣍⡀⠀⠀⣾⠀⡀⠀⠀⠀⠀⣿⡟⢻⠋⣻⣿⡇⠀⢿⡄⠀⠀
⠀⠀⠀⠀⡀⡜⠀⠀⠀⠀⠀⠀⣿⣿⡿⠋⠀⠐⢻⣿⣿⣿⡀⠈⣿⣦⡙⣄⠀⠸⡇⢸⠛⠛⠀⠀⠠⣾⣿⣿⣿⣦⡀⢸⠀⡇⠀⠀⠀⠀⣿⣶⣾⣿⣿⣿⠃⠀⢸⡇⠀⠀
⠀⠀⠀⠀⡆⠀⠀⠀⠀⠀⠀⢠⣿⡼⠃⠀⠀⣶⣾⣿⣿⣿⡇⠀⠈⢷⡙⢮⣀⠀⣿⠈⠄⠀⠀⢠⣤⣿⣿⣿⣿⣿⣿⣾⢲⡇⠀⠀⠀⠀⡿⣿⣿⣿⣿⡟⠀⠀⢸⣷⠀⠀
⠀⠀⠀⣤⡇⢰⠀⠀⠀⠀⠀⢸⣿⡇⠀⠀⠀⢻⡿⣿⣷⢿⠇⠀⠀⠀⠳⡄⠈⠳⢼⡀⠀⠀⠀⢸⣿⣿⣿⣿⣿⡟⢸⡏⣼⠁⠀⠀⢀⡶⣷⣿⣿⣿⣿⠃⠀⠀⠀⣿⠀⠀
⠀⠀⢰⣻⠀⢸⡇⠀⠀⠀⠀⣼⣿⣿⡄⠀⠀⠘⢧⣀⣰⠞⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠤⠀⣹⠁⢠⣣⠇⠀⠀⠀⢸⡇⣿⣿⣿⣿⣿⠀⠀⠀⠀⣿⠀⠀
⠀⠀⡄⠀⠀⢸⣇⠀⢀⠀⠀⣷⣿⡿⢿⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠒⠒⠚⠃⠀⣸⡿⠀⠀⠀⠀⢸⡇⣿⣿⣿⣿⣿⠀⠀⠀⠀⣿⠀⠀
⠀⢰⠁⠀⠀⠀⣿⡄⠘⢦⠀⣿⡫⠐⣺⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣿⠀⠀⠀⠀⠀⢸⣿⣿⣿⡿⠟⠁⠀⠀⠀⠀⠘⠀⠀
⠀⢸⠀⠀⠀⣷⣹⣷⠀⠈⡾⠋⠀⠀⣿⣳⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡼⢹⡇⣼⠀⠀⠀⠀⣼⣿⡟⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠈⠁⠀⠀⠀⢷⡻⢧⡞⠁⠉⠉⠭⣅⣈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠀⣼⣸⠃⠀⠀⠀⢀⣿⡏⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠁⠀⣿⣄⠀⠀⠀⠀⠈⠙⠳⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣷⡇⠀⠀⠀⡀⢸⡿⠀⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⡄⠀⠀⠀⠀⠀⠀⠀⠀⡟⢸⡷⣄⠀⠀⠀⠀⠀⠀⠉⠢⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⠴⣾⠙⣿⠁⠀⠀⢠⡇⣾⣷⣼⠥⠤⠤⣤⣄⣀⡀⠀⠀⠀⠀⠀
⡀⠀⠀⠀⠀⠀⠀⠀⢠⡇⣿⡇⣿⣳⣄⠀⠀⠀⠀⠀⠀⠈⠑⣦⣄⠀⠀⠀⠀⠀⠀⠀⢀⣠⡤⠒⠋⣀⡾⠃⢠⡏⠀⠀⢠⣿⣿⣯⣿⡏⢀⡔⠋⠁⠀⠈⠉⠲⡄⠀⠀⠀
⡇⠀⠀⠀⠀⠀⠀⠀⢸⡇⣿⣷⢸⣿⣿⡷⢤⠀⠀⠀⠀⠀⠀⠈⢻⣓⢦⣀⣀⣤⠶⠚⠉⠀⢀⡠⠞⠁⠀⢀⡾⠀⠀⢀⣾⣯⢿⣿⠋⠰⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⡃⠀⠀⠀⠀⠀⠀⠀⢸⡇⢸⣹⣯⣿⠃⢧⠀⡷⡄⠀⠀⠀⠀⠀⠀⢡⡿⠛⢙⣿⣦⣠⠴⠚⠉⠀⠀⢀⣠⡿⠁⠀⣠⣾⣯⡽⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇⢸⡇⠈⠻⡆⠀⡾⠁⠀⠀⠀⠀⠀⠀⢀⣾⣧⠴⢺⣿⡉⠀⠀⠀⠀⢀⣤⢾⡟⠁⢀⣴⠟⠉⠁⢸⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⡼⠀⠀⠀⢀⡼⠁⠀⠀⠀⠀⠀⠀⠀⣼⠋⠀⠀⠀⡝⢷⠀⢀⡤⠖⠋⣀⣮⠴⠚⠋⠁⠀⠀⢠⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⠁⠀⠀⢠⠞⠀⠀⠀⠀⠀⠀⠀⠀⣼⡇⠀⠀⢀⣼⣧⠈⡗⣿⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀⡾⠁⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢰⡇⠀⣠⣶⠃⠀⠀⠀⠀⠀⠀⠀⠀⣸⡿⠀⠀⢠⣾⠉⢸⢷⣼⣿⡇⠀⠀⠀⢀⡠⠊⠀⠀⠀⡼⠁⢰⠟⢹⡗⢶⣶⡶⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⡼⠀⣰⣿⢿⠀⠀⠀⠀⠀⠀⠀⠀⣴⣿⡇⠀⣰⠟⢹⠀⠀⠈⡽⠛⢷⡀⠀⠀⠁⠀⠀⠀⠀⣸⠁⢠⣾⠀⣼⠃⢠⡿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢀⣧⣾⣏⢹⣿⠀⠀⠀⠀⠀⠀⠀⡸⠋⢰⡁⢰⠏⣰⣿⠀⠀⣼⣧⡴⠛⣿⠀⠀⠀⠀⠀⢀⡼⠃⠀⠘⢿⣿⣃⣀⣿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll N = 1e5+9;
ll n , m , k , q;
ll a[N],b[N];
ll d[N];
ll l[N] , r[N];
multiset<ll> s;
vector<ll> v[N];
void rec(ll x)
{
memset(d,-1,sizeof(d));
ll vl = x , vr = x;
queue<pll> q;
q.push({x,0});
while(!q.empty())
{
auto itt = q.front();
q.pop();
ll nd = itt.F;
ll de = itt.S;
d[nd]=de;
for(int i = vr+1 ; r[nd]>=i ; i++)
q.push({i,de+1});
vr=max(vr,r[nd]);
for(int i = vl-1 ; i>=l[nd] ; i--)
q.push({i,de+1});
vl=min(vl,l[nd]);
}
}
int main()
{
d3
cin >> n >> k;
cin >> m;
for(int i = 1 ; m>=i ; i++)
cin >> a[i] >> b[i];
for(int i = 1 ; n>=i ; i++)
l[i]=i,r[i]=i;
for(int i = 1 ; m>=i ; i++)
{
if(a[i]<b[i])
{
v[a[i]].pb(b[i]);
v[min(a[i]+k-1,b[i]-1)+1].pb(-b[i]);
}
}
for(int i = 1 ; n>=i ; i++)
{
for(auto it : v[i])
{
if(it<0)
s.erase(s.find(-it));
else
s.in(it);
}
if(!s.empty())
r[i]=*(--s.end());
}
s.clear();
for(int i = 1 ; n>=i ; i++)
v[i].clear();
for(int i = 1 ; m>=i ; i++)
{
if(a[i]>b[i])
{
v[a[i]].pb(b[i]);
v[max(a[i]-k+1,b[i]+1)-1].pb(-b[i]);
}
}
for(int i = n ; i>0 ; i--)
{
for(auto it : v[i])
{
if(it<0)
s.erase(s.find(-it));
else
s.in(it);
}
if(!s.empty())
l[i]=*(s.begin());
}
cin >> q;
while(q--)
{
ll start , target;
cin >> start >> target;
rec(start);
cout << d[target] << "\n";
}
}
# | 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... |