//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
//#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
using namespace std;
struct Node{
int mx,mn;
void pull(Node a,Node b){
mx=max(a.mx,b.mx);
mn=min(a.mn,b.mn);
}
};
struct segment_tree{
Node seg[4*N],tag[4*N];
void push(int l,int r,int i){
if (tag[i].mx>0){
tag[2*i].mx=max(tag[2*i].mx,tag[i].mx);
tag[2*i+1].mx=max(tag[2*i+1].mx,tag[i].mx);
seg[2*i].mx=max(seg[2*i].mx,tag[i].mx);
seg[2*i+1].mx=max(seg[2*i+1].mx,tag[i].mx);
tag[i].mx=0;
}
if (tag[i].mn<1e8){
tag[2*i].mn=min(tag[2*i].mn,tag[i].mn);
tag[2*i+1].mn=min(tag[2*i+1].mn,tag[i].mn);
seg[2*i].mn=min(seg[2*i].mn,tag[i].mn);
seg[2*i+1].mn=min(seg[2*i+1].mn,tag[i].mn);
tag[i].mn=1e9;
}
}
void modify(int l,int r,int i,int ll,int rr,int vmx,int vmn){
if (ll>rr) return;
if (ll<=l&&rr>=r){
tag[i].mx=max(vmx,tag[i].mx);
seg[i].mx=max(seg[i].mx,tag[i].mx);
tag[i].mn=min(vmn,tag[i].mn);
seg[i].mn=min(seg[i].mn,tag[i].mn);
return;
}
int mid=(l+r)>>1;
push(l,r,i);
if (rr<=mid) modify(l,mid,2*i,ll,rr,vmx,vmn);
else if (ll>mid) modify(mid+1,r,2*i+1,ll,rr,vmx,vmn);
else {
modify(l,mid,2*i,ll,mid,vmx,vmn);
modify(mid+1,r,2*i+1,mid+1,rr,vmx,vmn);
}
seg[i].pull(seg[2*i],seg[2*i+1]);
}
Node query(int l,int r,int i,int ll,int rr){
if (ll>rr){
Node np; np.mn=1e9; np.mx=-1;
return np;
}
if (ll<=l&&rr>=r) return seg[i];
int mid=(l+r)>>1;
push(l,r,i);
if (rr<=mid) return query(l,mid,2*i,ll,rr);
else if (ll>mid) return query(mid+1,r,2*i+1,ll,rr);
else {
Node np;
np.pull(query(l,mid,2*i,ll,mid),query(mid+1,r,2*i+1,mid+1,rr));
return np;
}
}
}seg[30];
int n,k,m;
signed main(){
fast
cin>>n>>k>>m;
for (int j=0;j<30;j++){
for (int i=0;i<4*n+5;i++){
seg[j].seg[i].mx=-1;
seg[j].seg[i].mn=1e9;
seg[j].tag[i].mx=-1;
seg[j].tag[i].mn=1e9;
}
}
for (int i=1;i<=m;i++){
int a,b; cin>>a>>b;
if (a<b){
seg[0].modify(1,n,1,a,min(a+k-1,b),b,1e9);
}
else {
seg[0].modify(1,n,1,max(b,a-k+1),a,-1,b);
}
}
/*
for (int i=1;i<=n;i++){
Node np=seg[0].query(1,n,1,i,i);
cout<<"{"<<np.mx<<","<<np.mn<<"} ";
}
cout<<'\n';
*/
for (int i=1;i<25;i++){
for (int j=1;j<=n;j++){
Node qu=seg[i-1].query(1,n,1,j,j);
Node np=seg[i-1].query(1,n,1,min(qu.mn,j),max(qu.mx,j));
seg[i].modify(1,n,1,j,j,np.mx,np.mn);
// cout<<"{"<<np.mx<<","<<np.mn<<"} ";
}
// cout<<'\n';
}
int q; cin>>q;
while (q--){
int a,b,ans=0; cin>>a>>b;
Node np; np.mn=a; np.mx=a;
for (int i=23;i>=0;i--){
Node tans=seg[i].query(1,n,1,np.mn,np.mx);
if (a>b){
if (tans.mn>b){
ans+=(1LL<<i);
np.pull(np,tans);
}
}
else {
if (tans.mx<b){
ans+=(1LL<<i);
np.pull(np,tans);
}
}
}
if (ans>5000000) cout<<-1<<'\n';
else cout<<ans+1<<'\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1356 KB |
Output is correct |
2 |
Correct |
3 ms |
1356 KB |
Output is correct |
3 |
Correct |
2 ms |
1356 KB |
Output is correct |
4 |
Correct |
3 ms |
1356 KB |
Output is correct |
5 |
Correct |
3 ms |
1476 KB |
Output is correct |
6 |
Correct |
2 ms |
1356 KB |
Output is correct |
7 |
Correct |
3 ms |
1228 KB |
Output is correct |
8 |
Correct |
3 ms |
1356 KB |
Output is correct |
9 |
Correct |
4 ms |
1344 KB |
Output is correct |
10 |
Correct |
1 ms |
716 KB |
Output is correct |
11 |
Correct |
4 ms |
1356 KB |
Output is correct |
12 |
Correct |
9 ms |
1344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1356 KB |
Output is correct |
2 |
Correct |
3 ms |
1356 KB |
Output is correct |
3 |
Correct |
2 ms |
1356 KB |
Output is correct |
4 |
Correct |
3 ms |
1356 KB |
Output is correct |
5 |
Correct |
3 ms |
1476 KB |
Output is correct |
6 |
Correct |
2 ms |
1356 KB |
Output is correct |
7 |
Correct |
3 ms |
1228 KB |
Output is correct |
8 |
Correct |
3 ms |
1356 KB |
Output is correct |
9 |
Correct |
4 ms |
1344 KB |
Output is correct |
10 |
Correct |
1 ms |
716 KB |
Output is correct |
11 |
Correct |
4 ms |
1356 KB |
Output is correct |
12 |
Correct |
9 ms |
1344 KB |
Output is correct |
13 |
Correct |
17 ms |
4568 KB |
Output is correct |
14 |
Correct |
16 ms |
4576 KB |
Output is correct |
15 |
Correct |
14 ms |
4556 KB |
Output is correct |
16 |
Correct |
17 ms |
4580 KB |
Output is correct |
17 |
Correct |
18 ms |
4576 KB |
Output is correct |
18 |
Correct |
12 ms |
4556 KB |
Output is correct |
19 |
Correct |
16 ms |
4388 KB |
Output is correct |
20 |
Correct |
13 ms |
4556 KB |
Output is correct |
21 |
Correct |
11 ms |
4556 KB |
Output is correct |
22 |
Correct |
21 ms |
4580 KB |
Output is correct |
23 |
Correct |
19 ms |
4580 KB |
Output is correct |
24 |
Correct |
19 ms |
4572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1031 ms |
188228 KB |
Output is correct |
2 |
Correct |
954 ms |
188192 KB |
Output is correct |
3 |
Correct |
950 ms |
188184 KB |
Output is correct |
4 |
Correct |
878 ms |
188184 KB |
Output is correct |
5 |
Correct |
768 ms |
190264 KB |
Output is correct |
6 |
Correct |
956 ms |
190436 KB |
Output is correct |
7 |
Correct |
717 ms |
190136 KB |
Output is correct |
8 |
Correct |
688 ms |
187612 KB |
Output is correct |
9 |
Correct |
669 ms |
189272 KB |
Output is correct |
10 |
Correct |
1004 ms |
190424 KB |
Output is correct |
11 |
Correct |
890 ms |
190460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1287 ms |
189540 KB |
Output is correct |
2 |
Correct |
1340 ms |
191024 KB |
Output is correct |
3 |
Correct |
1431 ms |
190000 KB |
Output is correct |
4 |
Correct |
772 ms |
190608 KB |
Output is correct |
5 |
Correct |
892 ms |
189292 KB |
Output is correct |
6 |
Correct |
899 ms |
190936 KB |
Output is correct |
7 |
Correct |
1277 ms |
191012 KB |
Output is correct |
8 |
Correct |
1059 ms |
191028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1296 ms |
190868 KB |
Output is correct |
2 |
Correct |
1444 ms |
190200 KB |
Output is correct |
3 |
Correct |
1527 ms |
189440 KB |
Output is correct |
4 |
Correct |
1473 ms |
189184 KB |
Output is correct |
5 |
Correct |
1179 ms |
188916 KB |
Output is correct |
6 |
Correct |
1305 ms |
188796 KB |
Output is correct |
7 |
Correct |
1054 ms |
189920 KB |
Output is correct |
8 |
Correct |
4 ms |
1356 KB |
Output is correct |
9 |
Correct |
16 ms |
4576 KB |
Output is correct |
10 |
Correct |
1094 ms |
190392 KB |
Output is correct |
11 |
Correct |
1262 ms |
190904 KB |
Output is correct |
12 |
Correct |
1100 ms |
188956 KB |
Output is correct |
13 |
Correct |
1080 ms |
188400 KB |
Output is correct |
14 |
Correct |
2 ms |
1356 KB |
Output is correct |
15 |
Correct |
18 ms |
4544 KB |
Output is correct |
16 |
Correct |
1066 ms |
188264 KB |
Output is correct |
17 |
Correct |
1396 ms |
188404 KB |
Output is correct |
18 |
Correct |
1319 ms |
188356 KB |
Output is correct |
19 |
Correct |
1313 ms |
188484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1356 KB |
Output is correct |
2 |
Correct |
3 ms |
1356 KB |
Output is correct |
3 |
Correct |
2 ms |
1356 KB |
Output is correct |
4 |
Correct |
3 ms |
1356 KB |
Output is correct |
5 |
Correct |
3 ms |
1476 KB |
Output is correct |
6 |
Correct |
2 ms |
1356 KB |
Output is correct |
7 |
Correct |
3 ms |
1228 KB |
Output is correct |
8 |
Correct |
3 ms |
1356 KB |
Output is correct |
9 |
Correct |
4 ms |
1344 KB |
Output is correct |
10 |
Correct |
1 ms |
716 KB |
Output is correct |
11 |
Correct |
4 ms |
1356 KB |
Output is correct |
12 |
Correct |
9 ms |
1344 KB |
Output is correct |
13 |
Correct |
17 ms |
4568 KB |
Output is correct |
14 |
Correct |
16 ms |
4576 KB |
Output is correct |
15 |
Correct |
14 ms |
4556 KB |
Output is correct |
16 |
Correct |
17 ms |
4580 KB |
Output is correct |
17 |
Correct |
18 ms |
4576 KB |
Output is correct |
18 |
Correct |
12 ms |
4556 KB |
Output is correct |
19 |
Correct |
16 ms |
4388 KB |
Output is correct |
20 |
Correct |
13 ms |
4556 KB |
Output is correct |
21 |
Correct |
11 ms |
4556 KB |
Output is correct |
22 |
Correct |
21 ms |
4580 KB |
Output is correct |
23 |
Correct |
19 ms |
4580 KB |
Output is correct |
24 |
Correct |
19 ms |
4572 KB |
Output is correct |
25 |
Correct |
1031 ms |
188228 KB |
Output is correct |
26 |
Correct |
954 ms |
188192 KB |
Output is correct |
27 |
Correct |
950 ms |
188184 KB |
Output is correct |
28 |
Correct |
878 ms |
188184 KB |
Output is correct |
29 |
Correct |
768 ms |
190264 KB |
Output is correct |
30 |
Correct |
956 ms |
190436 KB |
Output is correct |
31 |
Correct |
717 ms |
190136 KB |
Output is correct |
32 |
Correct |
688 ms |
187612 KB |
Output is correct |
33 |
Correct |
669 ms |
189272 KB |
Output is correct |
34 |
Correct |
1004 ms |
190424 KB |
Output is correct |
35 |
Correct |
890 ms |
190460 KB |
Output is correct |
36 |
Correct |
1287 ms |
189540 KB |
Output is correct |
37 |
Correct |
1340 ms |
191024 KB |
Output is correct |
38 |
Correct |
1431 ms |
190000 KB |
Output is correct |
39 |
Correct |
772 ms |
190608 KB |
Output is correct |
40 |
Correct |
892 ms |
189292 KB |
Output is correct |
41 |
Correct |
899 ms |
190936 KB |
Output is correct |
42 |
Correct |
1277 ms |
191012 KB |
Output is correct |
43 |
Correct |
1059 ms |
191028 KB |
Output is correct |
44 |
Correct |
1296 ms |
190868 KB |
Output is correct |
45 |
Correct |
1444 ms |
190200 KB |
Output is correct |
46 |
Correct |
1527 ms |
189440 KB |
Output is correct |
47 |
Correct |
1473 ms |
189184 KB |
Output is correct |
48 |
Correct |
1179 ms |
188916 KB |
Output is correct |
49 |
Correct |
1305 ms |
188796 KB |
Output is correct |
50 |
Correct |
1054 ms |
189920 KB |
Output is correct |
51 |
Correct |
4 ms |
1356 KB |
Output is correct |
52 |
Correct |
16 ms |
4576 KB |
Output is correct |
53 |
Correct |
1094 ms |
190392 KB |
Output is correct |
54 |
Correct |
1262 ms |
190904 KB |
Output is correct |
55 |
Correct |
1100 ms |
188956 KB |
Output is correct |
56 |
Correct |
1080 ms |
188400 KB |
Output is correct |
57 |
Correct |
2 ms |
1356 KB |
Output is correct |
58 |
Correct |
18 ms |
4544 KB |
Output is correct |
59 |
Correct |
1066 ms |
188264 KB |
Output is correct |
60 |
Correct |
1396 ms |
188404 KB |
Output is correct |
61 |
Correct |
1319 ms |
188356 KB |
Output is correct |
62 |
Correct |
1313 ms |
188484 KB |
Output is correct |
63 |
Correct |
1190 ms |
188344 KB |
Output is correct |
64 |
Correct |
1480 ms |
188676 KB |
Output is correct |
65 |
Correct |
1224 ms |
188664 KB |
Output is correct |
66 |
Correct |
776 ms |
188772 KB |
Output is correct |
67 |
Correct |
1182 ms |
188496 KB |
Output is correct |
68 |
Correct |
1264 ms |
186556 KB |
Output is correct |
69 |
Correct |
841 ms |
188472 KB |
Output is correct |
70 |
Correct |
1279 ms |
188388 KB |
Output is correct |
71 |
Correct |
1369 ms |
188356 KB |
Output is correct |