#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())
ll n, K;
ll m;
ll q;
pll a[200010];
ll L, R;
pll b[200010];
ll Lspa[200010][21];
ll Rspa[200010][21];
struct segtree
{
pll seg[1000010][2];
pll lazy[1000010][2];
void init(ll no, ll s, ll e)
{
lazy[no][0] = {-INF, 0};
lazy[no][1] = {INF, 0};
seg[no][0] = {-INF, 0};
seg[no][1] = {INF, 0};
lazy[no << 1][0] = {-INF, 0};
lazy[no << 1][1] = {INF, 0};
seg[no << 1][0] = {-INF, 0};
seg[no << 1][1] = {INF, 0};
lazy[no << 1 | 1][0] = {-INF, 0};
lazy[no << 1 | 1][1] = {INF, 0};
seg[no << 1 | 1][0] = {-INF, 0};
seg[no << 1 | 1][1] = {INF, 0};
if(s == e)
return;
init(no << 1, s, (s + e) >> 1);
init(no << 1 | 1, ((s + e) >> 1) + 1, e);
}
void prop(ll no, ll s, ll e)
{
if(lazy[no][0].se)
{
if(seg[no][0].fi < lazy[no][0].fi)
seg[no][0] = lazy[no][0];
if(s != e)
{
if(lazy[no << 1][0].fi < lazy[no][0].fi)
lazy[no << 1][0] = lazy[no][0];
if(lazy[no << 1 | 1][0].fi < lazy[no][0].fi)
lazy[no << 1 | 1][0] = lazy[no][0];
}
lazy[no][0] = {-INF, 0};
}
if(lazy[no][1].se)
{
if(seg[no][1].fi > lazy[no][1].fi)
seg[no][1] = lazy[no][1];
if(s != e)
{
if(lazy[no << 1][1].fi > lazy[no][1].fi)
lazy[no << 1][1] = lazy[no][1];
if(lazy[no << 1 | 1][1].fi > lazy[no][1].fi)
lazy[no << 1 | 1][1] = lazy[no][1];
}
lazy[no][1] = {INF, 0};
}
}
void update(ll no, ll s, ll e, ll l, ll r, ll v1, ll v2)
{
prop(no, s, e);
if(e < l || r < s)
return;
if(l <= s && e <= r)
{
lazy[no][0] = lazy[no][1] = {v1, v2};
prop(no, s, e);
return;
}
update(no << 1, s, (s + e) >> 1, l, r, v1, v2);
update(no << 1 | 1, ((s + e) >> 1) + 1, e, l, r, v1, v2);
if(seg[no << 1][0].fi < seg[no << 1 | 1][0].fi)
seg[no][0] = seg[no << 1 | 1][0];
else
seg[no][0] = seg[no << 1][0];
if(seg[no << 1][1].fi > seg[no << 1 | 1][0].fi)
seg[no][1] = seg[no << 1 | 1][1];
else
seg[no][1] = seg[no << 1][1];
}
pair<pll, pll> query(ll no, ll s, ll e, ll l, ll r)
{
prop(no, s, e);
if(e < l || r < s)
return {{-INF, 0}, {INF, 0}};
if(l <= s && e <= r)
return {seg[no][0], seg[no][1]};
pair<pll, pll> LL = query(no << 1, s, (s + e) >> 1, l, r);
pair<pll, pll> RR = query(no << 1 | 1, ((s + e) >> 1) + 1, e, l, r);
pair<pll, pll> ret;
if(LL.fi.fi > RR.fi.fi)
ret.fi = LL.fi;
else
ret.fi = RR.fi;
if(LL.se.fi < RR.se.fi)
ret.se = LL.se;
else
ret.se = RR.se;
return ret;
}
}segt;
void RR(void)
{
ll cc = 0;
for(ll i = 1 ; i <= m ; i++)
{
if(a[i].fi < a[i].se)
b[cc++] = {a[i].fi, i};
}
sort(b, b + cc);
if(!cc)
return;
segt.init(1, 1, n);
ll num = b[cc - 1].se;
segt.update(1, 1, n, a[num].fi, min(a[num].se, a[num].fi + K - 1), a[num].se, num);
for(ll i = cc - 2 ; i >= 0 ; i--)
{
num = b[i].se;
pair<pll, pll> qry = segt.query(1, 1, n, a[num].fi, a[num].se);
if(qry.fi.se && a[num].se < qry.fi.fi)
Rspa[num][0] = qry.fi.se;
segt.update(1, 1, n, a[num].fi, min(a[num].se, a[num].fi + K - 1), a[num].se, num);
}
}
void LL(void)
{
ll cc = 0;
for(ll i = 1 ; i <= m ; i++)
{
if(a[i].fi > a[i].se)
b[cc++] = {a[i].fi, i};
}
sort(b, b + cc);
reverse(b, b + cc);
if(!cc)
return;
segt.init(1, 1, n);
ll num = b[cc - 1].se;
segt.update(1, 1, n, a[num].se, max(a[num].fi, a[num].se - K + 1), a[num].fi, num);
for(ll i = cc - 2 ; i >= 0 ; i--)
{
num = b[i].se;
pair<pll, pll> qry = segt.query(1, 1, n, a[num].se, a[num].fi);
if(qry.se.se)
Lspa[num][0] = qry.se.se;
segt.update(1, 1, n, a[num].se, max(a[num].fi, a[num].se - K + 1), a[num].fi, num);
}
}
int main(void)
{
fastio
cin >> n >> K;
cin >> m;
for(ll i = 1 ; i <= m ; i++)
cin >> a[i].fi >> a[i].se;
LL();
RR();
for(ll i = 1 ; i <= m ; i++)
{
if(!Lspa[i][0])
Lspa[i][0] = i;
if(!Rspa[i][0])
Rspa[i][0] = i;
}
for(ll i = 1 ; i <= 20 ; i++)
{
for(ll j = 1 ; j <= m ; j++)
Rspa[j][i] = Rspa[Rspa[j][i - 1]][i - 1];
}
cin >> q;
while(q--)
{
cin >> L >> R;
pair<pll, pll> num = segt.query(1, 1, n, L, L);
if(!num.fi.se)
{
cout << -1 en;
continue;
}
if(num.fi.fi >= R)
{
cout << 1 en;
continue;
}
ll ans = 1;
for(ll i = 20 ; i >= 0 ; i--)
{
if(a[Rspa[num.fi.se][i]].se < R)
{
ans += (1LL << i);
num.fi.se = Rspa[num.fi.se][i];
}
}
if(a[Rspa[num.fi.se][0]].se < R)
{
cout << -1 en;
continue;
}
cout << ans + 1 en;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
132 ms |
61984 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
148 ms |
61204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
488 ms |
105324 KB |
Output is correct |
2 |
Correct |
190 ms |
69452 KB |
Output is correct |
3 |
Correct |
118 ms |
51420 KB |
Output is correct |
4 |
Correct |
95 ms |
40652 KB |
Output is correct |
5 |
Correct |
63 ms |
35112 KB |
Output is correct |
6 |
Correct |
43 ms |
33700 KB |
Output is correct |
7 |
Correct |
128 ms |
69172 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
3 ms |
1492 KB |
Output is correct |
10 |
Correct |
369 ms |
105064 KB |
Output is correct |
11 |
Correct |
483 ms |
105192 KB |
Output is correct |
12 |
Correct |
409 ms |
107980 KB |
Output is correct |
13 |
Correct |
417 ms |
107680 KB |
Output is correct |
14 |
Correct |
1 ms |
596 KB |
Output is correct |
15 |
Correct |
3 ms |
1620 KB |
Output is correct |
16 |
Correct |
251 ms |
107468 KB |
Output is correct |
17 |
Correct |
343 ms |
108120 KB |
Output is correct |
18 |
Correct |
300 ms |
108132 KB |
Output is correct |
19 |
Correct |
286 ms |
108080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |