#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};
if(s == e)
return;
init(no << 1, s, (s + e) >> 1);
init(no << 1 | 1, ((s + e) >> 1) + 1, e);
//hmm...?
}
void prop(ll no, ll s, ll e)
{
if(lazy[no][0].se != 0)
{
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 != 0)
{
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)
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 |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
106 ms |
46464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
175 ms |
46364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
415 ms |
91672 KB |
Output is correct |
| 2 |
Correct |
190 ms |
54732 KB |
Output is correct |
| 3 |
Correct |
115 ms |
36132 KB |
Output is correct |
| 4 |
Correct |
66 ms |
24860 KB |
Output is correct |
| 5 |
Correct |
43 ms |
19272 KB |
Output is correct |
| 6 |
Correct |
38 ms |
17796 KB |
Output is correct |
| 7 |
Correct |
140 ms |
54692 KB |
Output is correct |
| 8 |
Correct |
1 ms |
468 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1364 KB |
Output is correct |
| 10 |
Correct |
352 ms |
90956 KB |
Output is correct |
| 11 |
Incorrect |
426 ms |
91676 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
