#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int base = 1<<17;
struct min_left {
vector<int> t;
void construct() { t.assign(2*base, INT_MAX); }
void update(int a, int b, int val) {
if(a==b) {
t[a+base] = min(t[a+base], val);
return;
}
a += base-1;
b += base+1;
while(a/2 != b/2) {
if(a%2==0) t[a+1] = min(t[a+1], val);
if(b%2==1) t[b-1] = min(t[b-1], val);
a/=2; b/=2;
}
}
int query(int x) {
int ans = INT_MAX;
x += base;
while(x > 0) {
ans = min(ans, t[x]);
x/=2;
}
return ans;
}
};
struct max_right {
vector<int> t;
void construct() { t.assign(2*base, 0); }
void update(int a, int b, int val) {
if(a==b) {
t[a+base] = max(t[a+base], val);
return;
}
a += base-1;
b += base+1;
while(a/2 != b/2) {
if(a%2==0) t[a+1] = max(t[a+1], val);
if(b%2==1) t[b-1] = max(t[b-1], val);
a/=2; b/=2;
}
}
int query(int x) {
int ans = 0;
x += base;
while(x > 0) {
ans = max(ans, t[x]);
x/=2;
}
return ans;
}
};
int maxlog = 16;
struct segm_tree_max {
vector<vector<int>> t;
void build() {
t.assign(maxlog+1, vector<int>(2*base, 0));
}
void update(int x, int val, int i) {
x += base;
t[i][x] = val;
x/=2;
while(x>0) {
t[i][x] = max(t[i][x+x], t[i][x+x+1]);
x/=2;
}
}
int query(int a, int b, int i) {
if(a==b) return t[i][a+base];
a+=base-1;
b+=base+1;
int ans = INT_MIN;
while(a/2!=b/2) {
if(a%2==0) ans = max(ans, t[i][a+1]);
if(b%2==1) ans = max(ans, t[i][b-1]);
a/=2; b/=2;
}
return ans;
}
};
struct segm_tree_min {
segm_tree_max stm;
void build() { stm.build(); }
void update(int x, int val, int i) { stm.update(x, -val, i); }
int query(int a, int b, int i) { return -stm.query(a, b, i); }
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n, k;
cin >> n >> k;
min_left ml; ml.construct();
max_right mr; mr.construct();
for(int i=1; i<=n; ++i) {
mr.update(i, i, i);
ml.update(i, i, i);
}
int m;
cin >> m;
for(int i=0; i<m; ++i) {
ll a, b;
cin >> a >> b;
if(a<b) {
mr.update(a, min(a+k-1, b-1), b);
} else {
ml.update(max(a-k+1, b+1), a, b);
}
}
vector<int> vml(n+1), vmr(n+1);
for(int i=1; i<=n; ++i) {
vml[i] = ml.query(i);
vmr[i] = mr.query(i);
}
segm_tree_max stmax; stmax.build();
segm_tree_min stmin; stmin.build();
for(int i=1; i<=n; ++i) {
stmax.update(i, vmr[i], 0);
stmin.update(i, vml[i], 0);
}
for(int x=1; x<=maxlog; ++x) {
for(int i=1; i<=n; ++i) {
stmax.update(i, stmax.query(stmin.query(i, i, x-1), stmax.query(i, i, x-1), x-1), x);
stmin.update(i, stmin.query(stmin.query(i, i, x-1), stmax.query(i, i, x-1), x-1), x);
}
}
int q;
cin >> q;
while(q--) {
int a, b;
cin >> a >> b;
ll ans = 0;
pair<int, int> inv = {a, a};
for(int i=maxlog; i>=0; --i) {
pair<int, int> new_inv = {stmin.query(inv.first, inv.second, i), stmax.query(inv.first, inv.second, i)};
if(new_inv.first <= b && b <= new_inv.second) continue;
inv = new_inv;
ans += 1LL<<i;
}
pair<int, int> new_inv = {stmin.query(inv.first, inv.second, 0), stmax.query(inv.first, inv.second, 0)};
if(new_inv.first <= b && b <= new_inv.second) cout << ans+1 << "\n";
else cout << "-1\n";
}
return 0;
}
# | 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... |