#pragma GCC optimize("Ofast","unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
#define pii pair<int,int>
#define endl '\n'
vector<pii> tmp;
inline pii comb(pii a,pii b){
return {min(a.first,b.first),max(a.second,b.second)};
}
struct seg{
int l,m,r;
int maxval=-INF,minval=INF;
int maxlz=-INF,minlz=INF;
seg *lc,*rc;
int rmax(){
return max(maxlz,maxval);
}
int rmin(){
return min(minlz,minval);
}
void pull(){
maxval=max(lc->rmax(),rc->rmax());
minval=min(lc->rmin(),rc->rmin());
}
void push(){
lc->maxlz=max(lc->maxlz,maxlz);
rc->maxlz=max(rc->maxlz,maxlz);
lc->minlz=min(lc->minlz,minlz);
rc->minlz=min(rc->minlz,minlz);
}
seg(int l1,int r1){
l=l1,r=r1;
m=(l+r)>>1;
if(r-l==1){
maxval=minval=maxlz=minlz=l1;
return;
}
lc=new seg(l,m);
rc=new seg(m,r);
pull();
}
void add(int a,int b,int x){
if(a<=l&&b>=r){
maxlz=max(maxlz,x);
minlz=min(minlz,x);
return;
}
push();
if(a<m){
lc->add(a,b,x);
}
if(b>m){
rc->add(a,b,x);
}
pull();
}
pii ask(int a,int b){
if(a<=l&&b>=r){
return {rmin(),rmax()};
}
pii ans={INF,-INF};
push();
if(a<m){
ans=comb(ans,lc->ask(a,b));
}
if(b>m){
ans=comb(ans,rc->ask(a,b));
}
pull();
return ans;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n,k;cin>>n>>k;
vector<seg*> v(18);
for(int i=0;i<18;i++){
v[i]=new seg(0,n);
}
vector<vector<pii>> dp(18,vector<pii>(n));
int m;cin>>m;
for(int i=0;i<m;i++){
int a,b;cin>>a>>b;a--;b--;
if(a<b){
int c=min(a+k,b);
v[0]->add(a,c,b);
}
else{
int c=max(b+1,a-k+1);
v[0]->add(c,a+1,b);
}
}
for(int j=0;j<n;j++){
dp[0][j]=v[0]->ask(j,j+1);
}
for(int i=1;i<18;i++){
for(int j=0;j<n;j++){
v[i]->add(j,j+1,dp[i-1][j].first);
v[i]->add(j,j+1,dp[i-1][j].second);
}
for(int j=0;j<n;j++){
int a,b;tie(a,b)=dp[i-1][j];
dp[i][j]=v[i]->ask(a,b+1);
}
}
int q;cin>>q;
for(int i=0;i<q;i++){
int a,b;cin>>a>>b;a--;b--;
if(a<b){
int ans=0;
int l=a,r=a;
bool flag=0;
for(int j=17;j>=0;j--){
int c,d;
tie(c,d)=v[j]->ask(l,r+1);
if(d<b){
ans+=(1<<(j-1));
l=c,r=d;
}
else{
flag=1;
}
}
if(flag==0){
cout<<-1<<endl;
}
else{
cout<<ans+1<<endl;
}
}
else{
int ans=0;
int l=a,r=a;
bool flag=0;
for(int j=17;j>=0;j--){
int c,d;
tie(c,d)=v[j]->ask(l,r+1);
if(c>b){
ans+=(1<<(j-1));
l=c,r=d;
}
else{
flag=1;
}
}
if(flag==0){
cout<<-1<<endl;
}
else{
cout<<ans+1<<endl;
}
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
980 KB |
Output is correct |
2 |
Correct |
3 ms |
980 KB |
Output is correct |
3 |
Correct |
2 ms |
980 KB |
Output is correct |
4 |
Correct |
3 ms |
980 KB |
Output is correct |
5 |
Correct |
3 ms |
980 KB |
Output is correct |
6 |
Correct |
2 ms |
980 KB |
Output is correct |
7 |
Correct |
4 ms |
980 KB |
Output is correct |
8 |
Correct |
2 ms |
980 KB |
Output is correct |
9 |
Correct |
3 ms |
980 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
3 ms |
980 KB |
Output is correct |
12 |
Correct |
3 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
980 KB |
Output is correct |
2 |
Correct |
3 ms |
980 KB |
Output is correct |
3 |
Correct |
2 ms |
980 KB |
Output is correct |
4 |
Correct |
3 ms |
980 KB |
Output is correct |
5 |
Correct |
3 ms |
980 KB |
Output is correct |
6 |
Correct |
2 ms |
980 KB |
Output is correct |
7 |
Correct |
4 ms |
980 KB |
Output is correct |
8 |
Correct |
2 ms |
980 KB |
Output is correct |
9 |
Correct |
3 ms |
980 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
3 ms |
980 KB |
Output is correct |
12 |
Correct |
3 ms |
980 KB |
Output is correct |
13 |
Correct |
22 ms |
5124 KB |
Output is correct |
14 |
Correct |
21 ms |
5128 KB |
Output is correct |
15 |
Correct |
16 ms |
5076 KB |
Output is correct |
16 |
Correct |
15 ms |
5076 KB |
Output is correct |
17 |
Correct |
24 ms |
5120 KB |
Output is correct |
18 |
Correct |
15 ms |
5128 KB |
Output is correct |
19 |
Correct |
18 ms |
4820 KB |
Output is correct |
20 |
Correct |
15 ms |
5076 KB |
Output is correct |
21 |
Correct |
11 ms |
5076 KB |
Output is correct |
22 |
Correct |
20 ms |
5124 KB |
Output is correct |
23 |
Correct |
20 ms |
5124 KB |
Output is correct |
24 |
Correct |
21 ms |
5124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1082 ms |
240588 KB |
Output is correct |
2 |
Correct |
1040 ms |
240652 KB |
Output is correct |
3 |
Correct |
1151 ms |
240580 KB |
Output is correct |
4 |
Correct |
1029 ms |
240656 KB |
Output is correct |
5 |
Correct |
799 ms |
240764 KB |
Output is correct |
6 |
Correct |
1048 ms |
240568 KB |
Output is correct |
7 |
Correct |
731 ms |
240588 KB |
Output is correct |
8 |
Correct |
699 ms |
238156 KB |
Output is correct |
9 |
Correct |
701 ms |
240620 KB |
Output is correct |
10 |
Correct |
1078 ms |
240596 KB |
Output is correct |
11 |
Correct |
1071 ms |
240584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1599 ms |
240692 KB |
Output is correct |
2 |
Correct |
1206 ms |
240556 KB |
Output is correct |
3 |
Correct |
1641 ms |
240592 KB |
Output is correct |
4 |
Correct |
1018 ms |
240592 KB |
Output is correct |
5 |
Correct |
995 ms |
238328 KB |
Output is correct |
6 |
Correct |
965 ms |
240656 KB |
Output is correct |
7 |
Correct |
1565 ms |
240648 KB |
Output is correct |
8 |
Correct |
1483 ms |
240584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1534 ms |
240576 KB |
Output is correct |
2 |
Correct |
1997 ms |
240652 KB |
Output is correct |
3 |
Correct |
1923 ms |
241332 KB |
Output is correct |
4 |
Correct |
1791 ms |
240892 KB |
Output is correct |
5 |
Correct |
1555 ms |
240844 KB |
Output is correct |
6 |
Correct |
1499 ms |
240664 KB |
Output is correct |
7 |
Correct |
1240 ms |
241700 KB |
Output is correct |
8 |
Correct |
3 ms |
980 KB |
Output is correct |
9 |
Correct |
18 ms |
5076 KB |
Output is correct |
10 |
Correct |
1026 ms |
242192 KB |
Output is correct |
11 |
Correct |
1188 ms |
242696 KB |
Output is correct |
12 |
Correct |
1282 ms |
240368 KB |
Output is correct |
13 |
Correct |
1251 ms |
242788 KB |
Output is correct |
14 |
Correct |
3 ms |
956 KB |
Output is correct |
15 |
Correct |
24 ms |
5144 KB |
Output is correct |
16 |
Correct |
1097 ms |
242268 KB |
Output is correct |
17 |
Correct |
1891 ms |
242952 KB |
Output is correct |
18 |
Correct |
1749 ms |
243104 KB |
Output is correct |
19 |
Correct |
1571 ms |
242828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
980 KB |
Output is correct |
2 |
Correct |
3 ms |
980 KB |
Output is correct |
3 |
Correct |
2 ms |
980 KB |
Output is correct |
4 |
Correct |
3 ms |
980 KB |
Output is correct |
5 |
Correct |
3 ms |
980 KB |
Output is correct |
6 |
Correct |
2 ms |
980 KB |
Output is correct |
7 |
Correct |
4 ms |
980 KB |
Output is correct |
8 |
Correct |
2 ms |
980 KB |
Output is correct |
9 |
Correct |
3 ms |
980 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
3 ms |
980 KB |
Output is correct |
12 |
Correct |
3 ms |
980 KB |
Output is correct |
13 |
Correct |
22 ms |
5124 KB |
Output is correct |
14 |
Correct |
21 ms |
5128 KB |
Output is correct |
15 |
Correct |
16 ms |
5076 KB |
Output is correct |
16 |
Correct |
15 ms |
5076 KB |
Output is correct |
17 |
Correct |
24 ms |
5120 KB |
Output is correct |
18 |
Correct |
15 ms |
5128 KB |
Output is correct |
19 |
Correct |
18 ms |
4820 KB |
Output is correct |
20 |
Correct |
15 ms |
5076 KB |
Output is correct |
21 |
Correct |
11 ms |
5076 KB |
Output is correct |
22 |
Correct |
20 ms |
5124 KB |
Output is correct |
23 |
Correct |
20 ms |
5124 KB |
Output is correct |
24 |
Correct |
21 ms |
5124 KB |
Output is correct |
25 |
Correct |
1082 ms |
240588 KB |
Output is correct |
26 |
Correct |
1040 ms |
240652 KB |
Output is correct |
27 |
Correct |
1151 ms |
240580 KB |
Output is correct |
28 |
Correct |
1029 ms |
240656 KB |
Output is correct |
29 |
Correct |
799 ms |
240764 KB |
Output is correct |
30 |
Correct |
1048 ms |
240568 KB |
Output is correct |
31 |
Correct |
731 ms |
240588 KB |
Output is correct |
32 |
Correct |
699 ms |
238156 KB |
Output is correct |
33 |
Correct |
701 ms |
240620 KB |
Output is correct |
34 |
Correct |
1078 ms |
240596 KB |
Output is correct |
35 |
Correct |
1071 ms |
240584 KB |
Output is correct |
36 |
Correct |
1599 ms |
240692 KB |
Output is correct |
37 |
Correct |
1206 ms |
240556 KB |
Output is correct |
38 |
Correct |
1641 ms |
240592 KB |
Output is correct |
39 |
Correct |
1018 ms |
240592 KB |
Output is correct |
40 |
Correct |
995 ms |
238328 KB |
Output is correct |
41 |
Correct |
965 ms |
240656 KB |
Output is correct |
42 |
Correct |
1565 ms |
240648 KB |
Output is correct |
43 |
Correct |
1483 ms |
240584 KB |
Output is correct |
44 |
Correct |
1534 ms |
240576 KB |
Output is correct |
45 |
Correct |
1997 ms |
240652 KB |
Output is correct |
46 |
Correct |
1923 ms |
241332 KB |
Output is correct |
47 |
Correct |
1791 ms |
240892 KB |
Output is correct |
48 |
Correct |
1555 ms |
240844 KB |
Output is correct |
49 |
Correct |
1499 ms |
240664 KB |
Output is correct |
50 |
Correct |
1240 ms |
241700 KB |
Output is correct |
51 |
Correct |
3 ms |
980 KB |
Output is correct |
52 |
Correct |
18 ms |
5076 KB |
Output is correct |
53 |
Correct |
1026 ms |
242192 KB |
Output is correct |
54 |
Correct |
1188 ms |
242696 KB |
Output is correct |
55 |
Correct |
1282 ms |
240368 KB |
Output is correct |
56 |
Correct |
1251 ms |
242788 KB |
Output is correct |
57 |
Correct |
3 ms |
956 KB |
Output is correct |
58 |
Correct |
24 ms |
5144 KB |
Output is correct |
59 |
Correct |
1097 ms |
242268 KB |
Output is correct |
60 |
Correct |
1891 ms |
242952 KB |
Output is correct |
61 |
Correct |
1749 ms |
243104 KB |
Output is correct |
62 |
Correct |
1571 ms |
242828 KB |
Output is correct |
63 |
Correct |
1753 ms |
241532 KB |
Output is correct |
64 |
Correct |
1961 ms |
241884 KB |
Output is correct |
65 |
Correct |
1802 ms |
241484 KB |
Output is correct |
66 |
Correct |
828 ms |
242908 KB |
Output is correct |
67 |
Correct |
1630 ms |
243040 KB |
Output is correct |
68 |
Correct |
1477 ms |
240368 KB |
Output is correct |
69 |
Correct |
986 ms |
242824 KB |
Output is correct |
70 |
Correct |
1593 ms |
242872 KB |
Output is correct |
71 |
Execution timed out |
2095 ms |
243008 KB |
Time limit exceeded |
72 |
Halted |
0 ms |
0 KB |
- |