#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=1e5+10,P=998244353;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
int n,k,m;
vector<pii> trn[2];
struct SegTreeMin{
int tree[MAX*4];
int lazy[MAX*4];
void init(int l,int r,int id) {
if (l==r) {
tree[id]=l;
lazy[id]=INF;
return;
}
int m=l+r>>1;
init(l,m,id<<1);
init(m+1,r,id<<1|1);
tree[id]=min(tree[id<<1],tree[id<<1|1]);
lazy[id]=INF;
}
void pd(int l,int r,int id) {
if (lazy[id]!=INF) {
lazy[id<<1]=min(lazy[id<<1],lazy[id]);
lazy[id<<1|1]=min(lazy[id<<1|1],lazy[id]);
tree[id<<1]=min(tree[id<<1],lazy[id]);
tree[id<<1|1]=min(tree[id<<1|1],lazy[id]);
lazy[id]=INF;
}
}
void update(int val,int L,int R,int l=1,int r=n,int id=1) {
// cout<<l<<" "<<r<<" "<<val<<" upd\n";
if (L<=l and r<=R) {
tree[id]=min(tree[id],val);
lazy[id]=min(lazy[id],val);
return;
}
int m=l+r>>1;
pd(l,r,id);
if (L<=m) update(val,L,R,l,m,id<<1);
if (m<R) update(val,L,R,m+1,r,id<<1|1);
tree[id]=min(tree[id<<1],tree[id<<1|1]);
}
int query(int L,int R,int l=1,int r=n,int id=1) {
// cout<<l<<" "<<r<<" "<<dir<<" "<<id<<" q\n";
if (L<=l and r<=R) return tree[id];
int m=l+r>>1;
pd(l,r,id);
int ans=INF;
if (L<=m) ans=min(ans,query(L,R,l,m,id<<1));
if (m<R) ans=min(ans,query(L,R,m+1,r,id<<1|1));
return ans;
}
};
struct SegTreeMax{
int tree[MAX*4];
int lazy[MAX*4];
void init(int l,int r,int id) {
if (l==r) {
tree[id]=l;
lazy[id]=0;
return;
}
int m=l+r>>1;
init(l,m,id<<1);
init(m+1,r,id<<1|1);
tree[id]=max(tree[id<<1],tree[id<<1|1]);
lazy[id]=0;
}
void build(int l,int r,int id) {
;
}
void pd(int l,int r,int id) {
if (lazy[id]!=0) {
lazy[id<<1]=max(lazy[id<<1],lazy[id]);
lazy[id<<1|1]=max(lazy[id<<1|1],lazy[id]);
tree[id<<1]=max(tree[id<<1],lazy[id]);
tree[id<<1|1]=max(tree[id<<1|1],lazy[id]);
lazy[id]=0;
}
}
void update(int val,int L,int R,int l=1,int r=n,int id=1) {
if (L<=l and r<=R) {
tree[id]=max(tree[id],val);
lazy[id]=max(lazy[id],val);
return;
}
int m=l+r>>1;
pd(l,r,id);
if (L<=m) update(val,L,R,l,m,id<<1);
if (m<R) update(val,L,R,m+1,r,id<<1|1);
tree[id]=max(tree[id<<1],tree[id<<1|1]);
}
int query(int L,int R,int l=1,int r=n,int id=1) {
// cout<<l<<" "<<r<<" "<<id<<" q\n";
if (L<=l and r<=R) {
// cout<<l<<" "<<r<<" "<<tree[id]<<"\n";
return tree[id];
}
int m=l+r>>1;
pd(l,r,id);
int ans=0;
if (L<=m) ans=max(ans,query(L,R,l,m,id<<1));
if (m<R) ans=max(ans,query(L,R,m+1,r,id<<1|1));
return ans;
}
};
SegTreeMin lft[18];
SegTreeMax rt[18];
bool extend(int &l,int &r,int t,int k) {
int nl=lft[k].query(l,r),nr=rt[k].query(l,r);
// cout<<nl<<" "<<nr<<" nl nr\n";
if (nl<=t and t<=nr) return false;
l=nl;r=nr;
return true;
}
void build(int k,int l=1,int r=n,int id=1) {
if (l==r) {
int farlft=lft[k-1].query(l,l),farrt=rt[k-1].query(l,l);
rt[k].tree[id]=rt[k-1].query(farlft,farrt);
rt[k].lazy[id]=0;
lft[k].tree[id]=lft[k-1].query(farlft,farrt);
lft[k].lazy[id]=INF;
return ;
}
int m=l+r>>1;
build(k,l,m,id<<1);
build(k,m+1,r,id<<1|1);
rt[k].tree[id]=max(rt[k].tree[id<<1],rt[k].tree[id<<1|1]);
rt[k].lazy[id]=0;
lft[k].tree[id]=min(lft[k].tree[id<<1],lft[k].tree[id<<1|1]);
lft[k].lazy[id]=INF;
}
int main() {
speed;
cin>>n>>k;
cin>>m;
for (int i=0;i<m;i++) {
int a,b;
cin>>a>>b;
trn[(a<b)].emplace_back(a,b);
}
lft[0].init(1,n,1);
rt[0].init(1,n,1);
for (pii i:trn[0]) {
int s=i.first,t=i.second;
lft[0].update(t,max(t,s-k+1),s);
// cout<<max(t,s-k+1)<<" "<<s<<" "<<t<<" lft\n";
}
// for (int i=1;i<=n;i++) cout<<lft[0].query(i,i)<<" ";
// cout<<"\n";
// for (int i=1;i<=n;i++) cout<<rt[0].query(i,i)<<" ";
// cout<<"\n";
for (pii i:trn[1]) {
int s=i.first,t=i.second;
rt[0].update(t,s,min(t,s+k-1));
// cout<<s<<" "<<min(t,s+k-1)<<" "<<t<<" rt\n";
}
// cout<<rt[0].query(3,5)<<" vvdfbgsdgbsgf\n";
for (int i=1;i<18;i++) {
build(i);
}
// for (int k=0;k<18;k++) {
// for (int i=1;i<=n;i++) cout<<lft[k].query(i,i)<<" ";
// cout<<"\n";
// for (int i=1;i<=n;i++) cout<<rt[k].query(i,i)<<" ";
// cout<<"\n\n";
// }
cout<<flush;
int q;
cin>>q;
while (q--) {
int s,t;
cin>>s>>t;
int l=s,r=s;
ll ans=0;
for (int k=18-1;k>=0;k--) {
bool suc=extend(l,r,t,k);
if (suc) ans+=(1<<k);
// cout<<k<<" "<<suc<<" ksuc\n";
}
if (!extend(l,r,t,0)) cout<<ans+1<<"\n";
else cout<<"-1\n";
}
return 0;
}
Compilation message
Main.cpp: In member function 'void SegTreeMin::init(int, int, int)':
Main.cpp:27:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
27 | int m=l+r>>1;
| ~^~
Main.cpp: In member function 'void SegTreeMin::update(int, int, int, int, int, int)':
Main.cpp:49:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int m=l+r>>1;
| ~^~
Main.cpp: In member function 'int SegTreeMin::query(int, int, int, int, int)':
Main.cpp:58:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | int m=l+r>>1;
| ~^~
Main.cpp: In member function 'void SegTreeMax::init(int, int, int)':
Main.cpp:76:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int m=l+r>>1;
| ~^~
Main.cpp: In member function 'void SegTreeMax::update(int, int, int, int, int, int)':
Main.cpp:100:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
100 | int m=l+r>>1;
| ~^~
Main.cpp: In member function 'int SegTreeMax::query(int, int, int, int, int)':
Main.cpp:112:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
112 | int m=l+r>>1;
| ~^~
Main.cpp: In function 'void build(int, int, int, int)':
Main.cpp:141:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
141 | int m=l+r>>1;
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
96852 KB |
Output is correct |
2 |
Correct |
14 ms |
96860 KB |
Output is correct |
3 |
Correct |
12 ms |
96832 KB |
Output is correct |
4 |
Correct |
13 ms |
96860 KB |
Output is correct |
5 |
Correct |
13 ms |
96860 KB |
Output is correct |
6 |
Correct |
12 ms |
96888 KB |
Output is correct |
7 |
Correct |
12 ms |
98908 KB |
Output is correct |
8 |
Correct |
12 ms |
96860 KB |
Output is correct |
9 |
Correct |
14 ms |
96860 KB |
Output is correct |
10 |
Correct |
11 ms |
96860 KB |
Output is correct |
11 |
Correct |
12 ms |
96856 KB |
Output is correct |
12 |
Correct |
13 ms |
96860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
96852 KB |
Output is correct |
2 |
Correct |
14 ms |
96860 KB |
Output is correct |
3 |
Correct |
12 ms |
96832 KB |
Output is correct |
4 |
Correct |
13 ms |
96860 KB |
Output is correct |
5 |
Correct |
13 ms |
96860 KB |
Output is correct |
6 |
Correct |
12 ms |
96888 KB |
Output is correct |
7 |
Correct |
12 ms |
98908 KB |
Output is correct |
8 |
Correct |
12 ms |
96860 KB |
Output is correct |
9 |
Correct |
14 ms |
96860 KB |
Output is correct |
10 |
Correct |
11 ms |
96860 KB |
Output is correct |
11 |
Correct |
12 ms |
96856 KB |
Output is correct |
12 |
Correct |
13 ms |
96860 KB |
Output is correct |
13 |
Correct |
29 ms |
97116 KB |
Output is correct |
14 |
Correct |
42 ms |
97104 KB |
Output is correct |
15 |
Correct |
23 ms |
97108 KB |
Output is correct |
16 |
Correct |
23 ms |
97128 KB |
Output is correct |
17 |
Correct |
28 ms |
97188 KB |
Output is correct |
18 |
Correct |
21 ms |
97116 KB |
Output is correct |
19 |
Correct |
26 ms |
97108 KB |
Output is correct |
20 |
Correct |
22 ms |
97116 KB |
Output is correct |
21 |
Correct |
17 ms |
97116 KB |
Output is correct |
22 |
Correct |
26 ms |
97172 KB |
Output is correct |
23 |
Correct |
27 ms |
97104 KB |
Output is correct |
24 |
Correct |
28 ms |
97116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
955 ms |
109484 KB |
Output is correct |
2 |
Correct |
877 ms |
109408 KB |
Output is correct |
3 |
Correct |
997 ms |
109604 KB |
Output is correct |
4 |
Correct |
870 ms |
109916 KB |
Output is correct |
5 |
Correct |
441 ms |
111520 KB |
Output is correct |
6 |
Correct |
920 ms |
110488 KB |
Output is correct |
7 |
Correct |
406 ms |
109032 KB |
Output is correct |
8 |
Correct |
388 ms |
106716 KB |
Output is correct |
9 |
Correct |
405 ms |
107200 KB |
Output is correct |
10 |
Correct |
843 ms |
109756 KB |
Output is correct |
11 |
Correct |
799 ms |
111548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1152 ms |
110936 KB |
Output is correct |
2 |
Correct |
1031 ms |
111948 KB |
Output is correct |
3 |
Correct |
1438 ms |
110744 KB |
Output is correct |
4 |
Correct |
634 ms |
111996 KB |
Output is correct |
5 |
Correct |
632 ms |
111916 KB |
Output is correct |
6 |
Correct |
666 ms |
112412 KB |
Output is correct |
7 |
Correct |
1157 ms |
111932 KB |
Output is correct |
8 |
Correct |
1140 ms |
112152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1139 ms |
112656 KB |
Output is correct |
2 |
Correct |
1591 ms |
110408 KB |
Output is correct |
3 |
Correct |
1560 ms |
108912 KB |
Output is correct |
4 |
Correct |
1465 ms |
109044 KB |
Output is correct |
5 |
Correct |
1181 ms |
109068 KB |
Output is correct |
6 |
Correct |
1232 ms |
108424 KB |
Output is correct |
7 |
Correct |
936 ms |
111620 KB |
Output is correct |
8 |
Correct |
13 ms |
100952 KB |
Output is correct |
9 |
Correct |
26 ms |
101200 KB |
Output is correct |
10 |
Correct |
766 ms |
113716 KB |
Output is correct |
11 |
Correct |
948 ms |
113256 KB |
Output is correct |
12 |
Correct |
956 ms |
112444 KB |
Output is correct |
13 |
Correct |
959 ms |
112300 KB |
Output is correct |
14 |
Correct |
13 ms |
98908 KB |
Output is correct |
15 |
Correct |
29 ms |
99068 KB |
Output is correct |
16 |
Correct |
908 ms |
111532 KB |
Output is correct |
17 |
Correct |
1466 ms |
112984 KB |
Output is correct |
18 |
Correct |
1341 ms |
113264 KB |
Output is correct |
19 |
Correct |
1253 ms |
112876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
96852 KB |
Output is correct |
2 |
Correct |
14 ms |
96860 KB |
Output is correct |
3 |
Correct |
12 ms |
96832 KB |
Output is correct |
4 |
Correct |
13 ms |
96860 KB |
Output is correct |
5 |
Correct |
13 ms |
96860 KB |
Output is correct |
6 |
Correct |
12 ms |
96888 KB |
Output is correct |
7 |
Correct |
12 ms |
98908 KB |
Output is correct |
8 |
Correct |
12 ms |
96860 KB |
Output is correct |
9 |
Correct |
14 ms |
96860 KB |
Output is correct |
10 |
Correct |
11 ms |
96860 KB |
Output is correct |
11 |
Correct |
12 ms |
96856 KB |
Output is correct |
12 |
Correct |
13 ms |
96860 KB |
Output is correct |
13 |
Correct |
29 ms |
97116 KB |
Output is correct |
14 |
Correct |
42 ms |
97104 KB |
Output is correct |
15 |
Correct |
23 ms |
97108 KB |
Output is correct |
16 |
Correct |
23 ms |
97128 KB |
Output is correct |
17 |
Correct |
28 ms |
97188 KB |
Output is correct |
18 |
Correct |
21 ms |
97116 KB |
Output is correct |
19 |
Correct |
26 ms |
97108 KB |
Output is correct |
20 |
Correct |
22 ms |
97116 KB |
Output is correct |
21 |
Correct |
17 ms |
97116 KB |
Output is correct |
22 |
Correct |
26 ms |
97172 KB |
Output is correct |
23 |
Correct |
27 ms |
97104 KB |
Output is correct |
24 |
Correct |
28 ms |
97116 KB |
Output is correct |
25 |
Correct |
955 ms |
109484 KB |
Output is correct |
26 |
Correct |
877 ms |
109408 KB |
Output is correct |
27 |
Correct |
997 ms |
109604 KB |
Output is correct |
28 |
Correct |
870 ms |
109916 KB |
Output is correct |
29 |
Correct |
441 ms |
111520 KB |
Output is correct |
30 |
Correct |
920 ms |
110488 KB |
Output is correct |
31 |
Correct |
406 ms |
109032 KB |
Output is correct |
32 |
Correct |
388 ms |
106716 KB |
Output is correct |
33 |
Correct |
405 ms |
107200 KB |
Output is correct |
34 |
Correct |
843 ms |
109756 KB |
Output is correct |
35 |
Correct |
799 ms |
111548 KB |
Output is correct |
36 |
Correct |
1152 ms |
110936 KB |
Output is correct |
37 |
Correct |
1031 ms |
111948 KB |
Output is correct |
38 |
Correct |
1438 ms |
110744 KB |
Output is correct |
39 |
Correct |
634 ms |
111996 KB |
Output is correct |
40 |
Correct |
632 ms |
111916 KB |
Output is correct |
41 |
Correct |
666 ms |
112412 KB |
Output is correct |
42 |
Correct |
1157 ms |
111932 KB |
Output is correct |
43 |
Correct |
1140 ms |
112152 KB |
Output is correct |
44 |
Correct |
1139 ms |
112656 KB |
Output is correct |
45 |
Correct |
1591 ms |
110408 KB |
Output is correct |
46 |
Correct |
1560 ms |
108912 KB |
Output is correct |
47 |
Correct |
1465 ms |
109044 KB |
Output is correct |
48 |
Correct |
1181 ms |
109068 KB |
Output is correct |
49 |
Correct |
1232 ms |
108424 KB |
Output is correct |
50 |
Correct |
936 ms |
111620 KB |
Output is correct |
51 |
Correct |
13 ms |
100952 KB |
Output is correct |
52 |
Correct |
26 ms |
101200 KB |
Output is correct |
53 |
Correct |
766 ms |
113716 KB |
Output is correct |
54 |
Correct |
948 ms |
113256 KB |
Output is correct |
55 |
Correct |
956 ms |
112444 KB |
Output is correct |
56 |
Correct |
959 ms |
112300 KB |
Output is correct |
57 |
Correct |
13 ms |
98908 KB |
Output is correct |
58 |
Correct |
29 ms |
99068 KB |
Output is correct |
59 |
Correct |
908 ms |
111532 KB |
Output is correct |
60 |
Correct |
1466 ms |
112984 KB |
Output is correct |
61 |
Correct |
1341 ms |
113264 KB |
Output is correct |
62 |
Correct |
1253 ms |
112876 KB |
Output is correct |
63 |
Correct |
1404 ms |
110296 KB |
Output is correct |
64 |
Correct |
1605 ms |
110888 KB |
Output is correct |
65 |
Correct |
1475 ms |
110284 KB |
Output is correct |
66 |
Correct |
471 ms |
111424 KB |
Output is correct |
67 |
Correct |
1290 ms |
111052 KB |
Output is correct |
68 |
Correct |
1072 ms |
111224 KB |
Output is correct |
69 |
Correct |
656 ms |
111384 KB |
Output is correct |
70 |
Correct |
1251 ms |
111272 KB |
Output is correct |
71 |
Correct |
1465 ms |
112500 KB |
Output is correct |