#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ll int
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 200010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
#define DEBUG 0
struct node{
int s,e,m,mx,mn,lazy_mx=-INF,lazy_mn=INF;
node *l,*r;
node(int ss,int ee){
s = ss; e = ee; m = (s + e) / 2;
mx = e; mn = s;
if (s != e){
l = new node(s,m); r = new node(m+1,e);
}
}
void prop(){
if (s == e) return;
l->lazy_mx = max(l->lazy_mx, lazy_mx);
r->lazy_mx = max(r->lazy_mx, lazy_mx);
l->mx = max(l->mx, lazy_mx);
r->mx = max(r->mx, lazy_mx);
l->lazy_mn = min(l->lazy_mn, lazy_mn);
r->lazy_mn = min(r->lazy_mn, lazy_mn);
l->mn = min(l->mn, lazy_mn);
r->mn = min(r->mn, lazy_mn);
lazy_mn = INF, lazy_mx = -INF;
}
void upd_mx(int a,int b,int c){
prop();
if (a <= s && e <= b){
mx = max(mx, c);
lazy_mx = max(lazy_mx, c);
}else if (a > e || s > b) return;
else{
l->upd_mx(a,b,c); r->upd_mx(a,b,c);
mx = max(l->mx, r->mx);
}
}
void upd_mn(int a,int b,int c){
prop();
if (a <= s && e <= b){
mn = min(mn, c);
lazy_mn = min(lazy_mn, c);
}else if (a > e || s > b) return;
else{
l->upd_mn(a,b,c); r->upd_mn(a,b,c);
mn = min(l->mn, r->mn);
}
}
pi qry(int a,int b){
prop();
if (a <= s && e <= b) return pi(mn, mx);
else if (a > e || s > b) return pi(INF, -INF);
else{
pi x = l->qry(a,b), y = r->qry(a,b);
return pi(min(x.f,y.f), max(x.s,y.s));
}
}
}*root;
inline int lg2(int x){
return 31 - __builtin_clz(x);
}
struct SparseTable{
int table[maxn][20];
int N;
bool mn;
SparseTable(vi &v, bool _mn){
N = v.size();
mn = _mn;
FOR(i,0,v.size()-1) table[i+1][0] = v[i];
FOR(k,1,19) FOR(i,1,N){
if (mn){
table[i][k] = min(table[i][k-1],table[min(i+(1<<(k-1)),N)][k-1]);
}else{
table[i][k] = max(table[i][k-1],table[min(i+(1<<(k-1)),N)][k-1]);
}
}
}
int qry(int a,int b){
int x = lg2(b-a+1);
if (mn) return min(table[a][x], table[b-(1<<x)+1][x]);
else return max(table[a][x], table[b-(1<<x)+1][x]);
}
}*min_table[20], *max_table[20];
int N,K,M,Q,A[maxn],B[maxn],S[maxn],T[maxn];
pi dp[maxn][21];
int32_t main(){
fast;
cin >> N >> K >> M;
FOR(i,1,M) cin >> A[i] >> B[i];
cin >> Q;
FOR(i,1,Q) cin >> S[i] >> T[i];
root = new node(1,N);
FOR(i,1,M){
if (A[i] < B[i]) root->upd_mx(A[i],min(A[i] + K - 1, B[i]), B[i]);
else root->upd_mn(max(B[i], A[i] - K + 1), A[i], B[i]);
}
vi mn, mx;
FOR(i,1,N){
dp[i][0] = root->qry(i,i);
mn.pb(dp[i][0].f); mx.pb(dp[i][0].s);
}
min_table[0] = new SparseTable(mn, 1);
max_table[0] = new SparseTable(mx, 0);
FOR(k,1,19){
FOR(i,1,N) dp[i][k] = pi(min_table[k-1]->qry(dp[i][k-1].f, dp[i][k-1].s), max_table[k-1]->qry(dp[i][k-1].f, dp[i][k-1].s));
vi mn,mx;
FOR(i,1,N) mn.pb(dp[i][k].f), mx.pb(dp[i][k].s);
min_table[k] = new SparseTable(mn,1);
max_table[k] = new SparseTable(mx, 0);
}
if (DEBUG) FOR(i,1,N) cout << dp[i][0].f << ' ' << dp[i][0].s << '\n';
FOR(i,1,Q){
pi cur = pi(S[i],S[i]);
int ans = 0;
if (DEBUG) cout << "QUERY " << i << '\n';
DEC(k,19,0) {
if (DEBUG) cout << cur.f << ' ' << cur.s << '\n';
pi x = pi(min_table[k]->qry(cur.f,cur.s), max_table[k]->qry(cur.f,cur.s));
if (!(x.f <= T[i] && T[i] <= x.s)){
ans += (1<<k);
cur = x;
}
}
pi x = pi(min_table[0]->qry(cur.f,cur.s), max_table[0]->qry(cur.f,cur.s));
if (x.f <= T[i] && T[i] <= x.s) cout << ans+1 << '\n';
else cout << -1 << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1748 KB |
Output is correct |
2 |
Correct |
3 ms |
1684 KB |
Output is correct |
3 |
Correct |
2 ms |
1732 KB |
Output is correct |
4 |
Correct |
2 ms |
1748 KB |
Output is correct |
5 |
Correct |
2 ms |
1748 KB |
Output is correct |
6 |
Correct |
2 ms |
1724 KB |
Output is correct |
7 |
Correct |
3 ms |
1748 KB |
Output is correct |
8 |
Correct |
2 ms |
1748 KB |
Output is correct |
9 |
Correct |
2 ms |
1736 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
11 |
Correct |
2 ms |
1732 KB |
Output is correct |
12 |
Correct |
2 ms |
1748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1748 KB |
Output is correct |
2 |
Correct |
3 ms |
1684 KB |
Output is correct |
3 |
Correct |
2 ms |
1732 KB |
Output is correct |
4 |
Correct |
2 ms |
1748 KB |
Output is correct |
5 |
Correct |
2 ms |
1748 KB |
Output is correct |
6 |
Correct |
2 ms |
1724 KB |
Output is correct |
7 |
Correct |
3 ms |
1748 KB |
Output is correct |
8 |
Correct |
2 ms |
1748 KB |
Output is correct |
9 |
Correct |
2 ms |
1736 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
11 |
Correct |
2 ms |
1732 KB |
Output is correct |
12 |
Correct |
2 ms |
1748 KB |
Output is correct |
13 |
Correct |
13 ms |
7764 KB |
Output is correct |
14 |
Correct |
9 ms |
7700 KB |
Output is correct |
15 |
Correct |
7 ms |
7768 KB |
Output is correct |
16 |
Correct |
9 ms |
7760 KB |
Output is correct |
17 |
Correct |
10 ms |
7740 KB |
Output is correct |
18 |
Correct |
9 ms |
7764 KB |
Output is correct |
19 |
Correct |
10 ms |
7384 KB |
Output is correct |
20 |
Correct |
8 ms |
7768 KB |
Output is correct |
21 |
Correct |
8 ms |
7692 KB |
Output is correct |
22 |
Correct |
9 ms |
7676 KB |
Output is correct |
23 |
Correct |
12 ms |
7764 KB |
Output is correct |
24 |
Correct |
9 ms |
7764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
785 ms |
345792 KB |
Output is correct |
2 |
Correct |
635 ms |
346452 KB |
Output is correct |
3 |
Correct |
654 ms |
346752 KB |
Output is correct |
4 |
Correct |
639 ms |
346488 KB |
Output is correct |
5 |
Correct |
834 ms |
348752 KB |
Output is correct |
6 |
Correct |
746 ms |
348912 KB |
Output is correct |
7 |
Correct |
663 ms |
348440 KB |
Output is correct |
8 |
Correct |
636 ms |
343304 KB |
Output is correct |
9 |
Correct |
658 ms |
346864 KB |
Output is correct |
10 |
Correct |
708 ms |
349132 KB |
Output is correct |
11 |
Correct |
724 ms |
348852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
664 ms |
346296 KB |
Output is correct |
2 |
Correct |
864 ms |
349760 KB |
Output is correct |
3 |
Correct |
699 ms |
347660 KB |
Output is correct |
4 |
Correct |
680 ms |
349356 KB |
Output is correct |
5 |
Correct |
797 ms |
346132 KB |
Output is correct |
6 |
Correct |
825 ms |
349664 KB |
Output is correct |
7 |
Correct |
774 ms |
349640 KB |
Output is correct |
8 |
Correct |
770 ms |
349656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
899 ms |
347136 KB |
Output is correct |
2 |
Correct |
697 ms |
347676 KB |
Output is correct |
3 |
Correct |
649 ms |
346760 KB |
Output is correct |
4 |
Correct |
616 ms |
346116 KB |
Output is correct |
5 |
Correct |
613 ms |
345852 KB |
Output is correct |
6 |
Correct |
566 ms |
345968 KB |
Output is correct |
7 |
Correct |
611 ms |
347764 KB |
Output is correct |
8 |
Correct |
2 ms |
1748 KB |
Output is correct |
9 |
Correct |
8 ms |
7764 KB |
Output is correct |
10 |
Correct |
773 ms |
348752 KB |
Output is correct |
11 |
Correct |
792 ms |
349612 KB |
Output is correct |
12 |
Correct |
779 ms |
346096 KB |
Output is correct |
13 |
Correct |
780 ms |
349636 KB |
Output is correct |
14 |
Correct |
2 ms |
1748 KB |
Output is correct |
15 |
Correct |
9 ms |
7796 KB |
Output is correct |
16 |
Correct |
661 ms |
348656 KB |
Output is correct |
17 |
Correct |
786 ms |
349744 KB |
Output is correct |
18 |
Correct |
773 ms |
349636 KB |
Output is correct |
19 |
Correct |
750 ms |
349612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1748 KB |
Output is correct |
2 |
Correct |
3 ms |
1684 KB |
Output is correct |
3 |
Correct |
2 ms |
1732 KB |
Output is correct |
4 |
Correct |
2 ms |
1748 KB |
Output is correct |
5 |
Correct |
2 ms |
1748 KB |
Output is correct |
6 |
Correct |
2 ms |
1724 KB |
Output is correct |
7 |
Correct |
3 ms |
1748 KB |
Output is correct |
8 |
Correct |
2 ms |
1748 KB |
Output is correct |
9 |
Correct |
2 ms |
1736 KB |
Output is correct |
10 |
Correct |
1 ms |
724 KB |
Output is correct |
11 |
Correct |
2 ms |
1732 KB |
Output is correct |
12 |
Correct |
2 ms |
1748 KB |
Output is correct |
13 |
Correct |
13 ms |
7764 KB |
Output is correct |
14 |
Correct |
9 ms |
7700 KB |
Output is correct |
15 |
Correct |
7 ms |
7768 KB |
Output is correct |
16 |
Correct |
9 ms |
7760 KB |
Output is correct |
17 |
Correct |
10 ms |
7740 KB |
Output is correct |
18 |
Correct |
9 ms |
7764 KB |
Output is correct |
19 |
Correct |
10 ms |
7384 KB |
Output is correct |
20 |
Correct |
8 ms |
7768 KB |
Output is correct |
21 |
Correct |
8 ms |
7692 KB |
Output is correct |
22 |
Correct |
9 ms |
7676 KB |
Output is correct |
23 |
Correct |
12 ms |
7764 KB |
Output is correct |
24 |
Correct |
9 ms |
7764 KB |
Output is correct |
25 |
Correct |
785 ms |
345792 KB |
Output is correct |
26 |
Correct |
635 ms |
346452 KB |
Output is correct |
27 |
Correct |
654 ms |
346752 KB |
Output is correct |
28 |
Correct |
639 ms |
346488 KB |
Output is correct |
29 |
Correct |
834 ms |
348752 KB |
Output is correct |
30 |
Correct |
746 ms |
348912 KB |
Output is correct |
31 |
Correct |
663 ms |
348440 KB |
Output is correct |
32 |
Correct |
636 ms |
343304 KB |
Output is correct |
33 |
Correct |
658 ms |
346864 KB |
Output is correct |
34 |
Correct |
708 ms |
349132 KB |
Output is correct |
35 |
Correct |
724 ms |
348852 KB |
Output is correct |
36 |
Correct |
664 ms |
346296 KB |
Output is correct |
37 |
Correct |
864 ms |
349760 KB |
Output is correct |
38 |
Correct |
699 ms |
347660 KB |
Output is correct |
39 |
Correct |
680 ms |
349356 KB |
Output is correct |
40 |
Correct |
797 ms |
346132 KB |
Output is correct |
41 |
Correct |
825 ms |
349664 KB |
Output is correct |
42 |
Correct |
774 ms |
349640 KB |
Output is correct |
43 |
Correct |
770 ms |
349656 KB |
Output is correct |
44 |
Correct |
899 ms |
347136 KB |
Output is correct |
45 |
Correct |
697 ms |
347676 KB |
Output is correct |
46 |
Correct |
649 ms |
346760 KB |
Output is correct |
47 |
Correct |
616 ms |
346116 KB |
Output is correct |
48 |
Correct |
613 ms |
345852 KB |
Output is correct |
49 |
Correct |
566 ms |
345968 KB |
Output is correct |
50 |
Correct |
611 ms |
347764 KB |
Output is correct |
51 |
Correct |
2 ms |
1748 KB |
Output is correct |
52 |
Correct |
8 ms |
7764 KB |
Output is correct |
53 |
Correct |
773 ms |
348752 KB |
Output is correct |
54 |
Correct |
792 ms |
349612 KB |
Output is correct |
55 |
Correct |
779 ms |
346096 KB |
Output is correct |
56 |
Correct |
780 ms |
349636 KB |
Output is correct |
57 |
Correct |
2 ms |
1748 KB |
Output is correct |
58 |
Correct |
9 ms |
7796 KB |
Output is correct |
59 |
Correct |
661 ms |
348656 KB |
Output is correct |
60 |
Correct |
786 ms |
349744 KB |
Output is correct |
61 |
Correct |
773 ms |
349636 KB |
Output is correct |
62 |
Correct |
750 ms |
349612 KB |
Output is correct |
63 |
Correct |
691 ms |
347236 KB |
Output is correct |
64 |
Correct |
699 ms |
347516 KB |
Output is correct |
65 |
Correct |
677 ms |
347328 KB |
Output is correct |
66 |
Correct |
805 ms |
349840 KB |
Output is correct |
67 |
Correct |
778 ms |
349576 KB |
Output is correct |
68 |
Correct |
766 ms |
346144 KB |
Output is correct |
69 |
Correct |
799 ms |
349540 KB |
Output is correct |
70 |
Correct |
740 ms |
349640 KB |
Output is correct |
71 |
Correct |
782 ms |
349692 KB |
Output is correct |