#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],ri[N];
multiset<ll> s;
vector<ll> v[N];
ll p[N][20];
ll po[20];
ll st , tr;
ll seg[4*N];
ll c[N];
void sb(ll x , ll l , ll r)
{
if(l==r)
{
seg[x]=c[l];
return;
}
sb(lc,l,mid);
sb(rc,mid+1,r);
seg[x]=max(seg[lc],seg[rc]);
}
ll sg(ll x , ll l , ll r , ll l1 , ll r1)
{
if(l>r1||r<l1)
return 0;
if(l>=l1&&r<=r1)
return seg[x];
return max(sg(lc,l,mid,l1,r1),sg(rc,mid+1,r,l1,r1));
}
bool check(ll x)
{
ll f1 = st;
ll y = x;
for(int j = 19 ; j>=0 ; j--)
{
if(y>=po[j])
{
y-=po[j];
f1=p[f1][j];
}
}
if(f1>=tr)
return 1;
else
return 0;
}
ll mx(ll l , ll r)
{
return sg(1,1,n,l,r);
}
int main()
{
d3
po[0]=1;
for(int i = 1 ; 20>i ; i++)
po[i]=po[i-1]*2;
cin >> n >> k;
cin >> m;
for(int i = 1 ; m>=i ; i++)
cin >> a[i] >> b[i];
for(int i = 1 ; n>=i ; i++)
ri[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())
ri[i]=*(--s.end());
}
for(int i = 1 ; n>=i ; i++)
p[i][0]=ri[i];
for(int j = 1 ; 20>j ; j++)
{
for(int i = 1 ; n>=i ; i++)
c[i]=p[i][j-1];
sb(1,1,n);
for(int i = 1 ; n>=i ; i++)
p[i][j]=mx(i,p[i][j-1]);
}
cin >> q;
while(q--)
{
cin >> st >> tr;
ll l = 1 , r = n;
ll ans = -1;
while(l<=r)
{
if(check(mid))
ans=mid,r=mid-1;
else
l=mid+1;
}
cans
}
}
# | 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... |