#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=1e6+5, MK=20;
int N,K,M,Q;
int L[MX],R[MX], A[MX], B[MX];
struct segtree {
pair<int,int> t[4 * MX];
// I define t[v] to be the range within reach from v by using 2^k steps
pair<int,int> merge(pair<int,int> a, pair<int, int> b) {
int l=min(a.first,b.first);
int r=max(a.second,b.second);
return make_pair(l,r);
}
void update(int v, int l, int r, int pos, pair<int,int> val) {
if(l > pos || r < pos) return;
if(l == r) {
t[v] = val;
return;
}
int mid = (l + r) >> 1;
update(v * 2 + 0, l, mid + 0, pos, val);
update(v * 2 + 1, mid + 1, r, pos, val);
t[v] = merge(t[v * 2 + 0], t[v * 2 + 1]);
}
pair<int,int> query(int v, int l, int r, int ql, int qr) {
if(ql > r || qr < l) return make_pair(1e9,0);
if(ql <= l && qr >= r) return t[v];
int mid = (l + r) >> 1;
return merge(query(v * 2 + 0, l, mid + 0, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
}
void reset() {
for(int i=0;i<4*MX;i++)
t[i]=make_pair(1e9,0);
}
} ST[MK];
vector<int> opens[MX], closes[MX];
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>N>>K>>M;
for(int i=1;i<=M;i++) {
cin>>A[i]>>B[i];
if(A[i]<B[i]) {
opens[A[i]].push_back(B[i]);
closes[min(A[i]+K-1,B[i]-1)].push_back(B[i]);
}
}
multiset<int> st;
for(int i=1;i<=N;i++) {
for(auto j:opens[i]) {
st.insert(j);
}
if(st.size())
R[i]=*st.rbegin();
else
R[i]=i;
for(auto j:closes[i]) {
st.erase(st.find(j));
}
}
for(int i=1;i<=N;i++) {
opens[i].clear();
closes[i].clear();
}
for(int i=1;i<=M;i++) {
if(A[i]>B[i]) {
opens[A[i]].push_back(B[i]);
closes[max(A[i]-K+1,B[i]+1)].push_back(B[i]);
}
}
st.clear();
for(int i=N;i>=1;i--) {
for(auto j:opens[i]) {
st.insert(j);
}
if(st.size())
L[i]=*st.begin();
else
L[i]=i;
for(auto j:closes[i]) {
st.erase(st.find(j));
}
}
for(int i=1;i<=N;i++) {
ST[0].update(1,1,N,i,make_pair(L[i],R[i]));
}
for(int k=1;k<MK;k++) {
for(int i=1;i<=N;i++) {
auto [l,r]=ST[k-1].query(1,1,N,i,i);
auto [nxtL,nxtR]=ST[k-1].query(1,1,N,l,r);
ST[k].update(1,1,N,i,make_pair(nxtL,nxtR));
}
}
cin>>Q;
for(int i=1;i<=Q;i++) {
int s,t;
cin>>s>>t;
auto [l,r]=ST[MK-1].query(1,1,N,s,s);
if(t<l||t>r) {
cout<<-1<<'\n';
continue;
}
int curL=s,curR=s,ans=0;
for(int k=MK-1;k>=0;k--) {
int nxtL=ST[k].query(1,1,N,curL,curR).first;
int nxtR=ST[k].query(1,1,N,curL,curR).second;
assert(nxtL<=nxtR);
if(!(nxtL<=t&&t<=nxtR)) {
ans+=1<<k;
curL=nxtL;
curR=nxtR;
}
}
cout<<ans+1<<'\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
72476 KB |
Output is correct |
2 |
Correct |
16 ms |
68496 KB |
Output is correct |
3 |
Correct |
15 ms |
70592 KB |
Output is correct |
4 |
Correct |
15 ms |
68596 KB |
Output is correct |
5 |
Correct |
18 ms |
66444 KB |
Output is correct |
6 |
Correct |
16 ms |
66532 KB |
Output is correct |
7 |
Correct |
15 ms |
64416 KB |
Output is correct |
8 |
Correct |
15 ms |
66528 KB |
Output is correct |
9 |
Correct |
16 ms |
66396 KB |
Output is correct |
10 |
Correct |
13 ms |
66396 KB |
Output is correct |
11 |
Correct |
14 ms |
66392 KB |
Output is correct |
12 |
Correct |
14 ms |
66396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
72476 KB |
Output is correct |
2 |
Correct |
16 ms |
68496 KB |
Output is correct |
3 |
Correct |
15 ms |
70592 KB |
Output is correct |
4 |
Correct |
15 ms |
68596 KB |
Output is correct |
5 |
Correct |
18 ms |
66444 KB |
Output is correct |
6 |
Correct |
16 ms |
66532 KB |
Output is correct |
7 |
Correct |
15 ms |
64416 KB |
Output is correct |
8 |
Correct |
15 ms |
66528 KB |
Output is correct |
9 |
Correct |
16 ms |
66396 KB |
Output is correct |
10 |
Correct |
13 ms |
66396 KB |
Output is correct |
11 |
Correct |
14 ms |
66392 KB |
Output is correct |
12 |
Correct |
14 ms |
66396 KB |
Output is correct |
13 |
Correct |
28 ms |
66768 KB |
Output is correct |
14 |
Correct |
27 ms |
64932 KB |
Output is correct |
15 |
Correct |
23 ms |
62812 KB |
Output is correct |
16 |
Correct |
20 ms |
62812 KB |
Output is correct |
17 |
Correct |
26 ms |
62896 KB |
Output is correct |
18 |
Correct |
23 ms |
62812 KB |
Output is correct |
19 |
Correct |
28 ms |
62812 KB |
Output is correct |
20 |
Correct |
24 ms |
62808 KB |
Output is correct |
21 |
Correct |
19 ms |
62808 KB |
Output is correct |
22 |
Correct |
28 ms |
62728 KB |
Output is correct |
23 |
Correct |
26 ms |
62808 KB |
Output is correct |
24 |
Correct |
25 ms |
62812 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
686 ms |
106564 KB |
Output is correct |
2 |
Correct |
661 ms |
106064 KB |
Output is correct |
3 |
Correct |
687 ms |
107220 KB |
Output is correct |
4 |
Correct |
679 ms |
105844 KB |
Output is correct |
5 |
Correct |
507 ms |
108120 KB |
Output is correct |
6 |
Correct |
676 ms |
107396 KB |
Output is correct |
7 |
Correct |
464 ms |
110020 KB |
Output is correct |
8 |
Correct |
446 ms |
106292 KB |
Output is correct |
9 |
Correct |
465 ms |
110924 KB |
Output is correct |
10 |
Correct |
633 ms |
112724 KB |
Output is correct |
11 |
Correct |
602 ms |
111176 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
916 ms |
112900 KB |
Output is correct |
2 |
Correct |
637 ms |
114092 KB |
Output is correct |
3 |
Correct |
1075 ms |
113336 KB |
Output is correct |
4 |
Correct |
656 ms |
116728 KB |
Output is correct |
5 |
Correct |
685 ms |
114632 KB |
Output is correct |
6 |
Correct |
666 ms |
114000 KB |
Output is correct |
7 |
Correct |
928 ms |
112268 KB |
Output is correct |
8 |
Correct |
885 ms |
113864 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
737 ms |
114860 KB |
Output is correct |
2 |
Correct |
1140 ms |
112964 KB |
Output is correct |
3 |
Correct |
1125 ms |
108344 KB |
Output is correct |
4 |
Correct |
1029 ms |
105168 KB |
Output is correct |
5 |
Correct |
882 ms |
102304 KB |
Output is correct |
6 |
Correct |
889 ms |
102268 KB |
Output is correct |
7 |
Correct |
808 ms |
110624 KB |
Output is correct |
8 |
Correct |
15 ms |
66392 KB |
Output is correct |
9 |
Correct |
27 ms |
66908 KB |
Output is correct |
10 |
Correct |
666 ms |
111020 KB |
Output is correct |
11 |
Correct |
831 ms |
112660 KB |
Output is correct |
12 |
Correct |
865 ms |
112844 KB |
Output is correct |
13 |
Correct |
868 ms |
115356 KB |
Output is correct |
14 |
Correct |
15 ms |
64344 KB |
Output is correct |
15 |
Correct |
31 ms |
66712 KB |
Output is correct |
16 |
Correct |
708 ms |
110184 KB |
Output is correct |
17 |
Correct |
1075 ms |
111184 KB |
Output is correct |
18 |
Correct |
1027 ms |
110636 KB |
Output is correct |
19 |
Correct |
978 ms |
110716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
72476 KB |
Output is correct |
2 |
Correct |
16 ms |
68496 KB |
Output is correct |
3 |
Correct |
15 ms |
70592 KB |
Output is correct |
4 |
Correct |
15 ms |
68596 KB |
Output is correct |
5 |
Correct |
18 ms |
66444 KB |
Output is correct |
6 |
Correct |
16 ms |
66532 KB |
Output is correct |
7 |
Correct |
15 ms |
64416 KB |
Output is correct |
8 |
Correct |
15 ms |
66528 KB |
Output is correct |
9 |
Correct |
16 ms |
66396 KB |
Output is correct |
10 |
Correct |
13 ms |
66396 KB |
Output is correct |
11 |
Correct |
14 ms |
66392 KB |
Output is correct |
12 |
Correct |
14 ms |
66396 KB |
Output is correct |
13 |
Correct |
28 ms |
66768 KB |
Output is correct |
14 |
Correct |
27 ms |
64932 KB |
Output is correct |
15 |
Correct |
23 ms |
62812 KB |
Output is correct |
16 |
Correct |
20 ms |
62812 KB |
Output is correct |
17 |
Correct |
26 ms |
62896 KB |
Output is correct |
18 |
Correct |
23 ms |
62812 KB |
Output is correct |
19 |
Correct |
28 ms |
62812 KB |
Output is correct |
20 |
Correct |
24 ms |
62808 KB |
Output is correct |
21 |
Correct |
19 ms |
62808 KB |
Output is correct |
22 |
Correct |
28 ms |
62728 KB |
Output is correct |
23 |
Correct |
26 ms |
62808 KB |
Output is correct |
24 |
Correct |
25 ms |
62812 KB |
Output is correct |
25 |
Correct |
686 ms |
106564 KB |
Output is correct |
26 |
Correct |
661 ms |
106064 KB |
Output is correct |
27 |
Correct |
687 ms |
107220 KB |
Output is correct |
28 |
Correct |
679 ms |
105844 KB |
Output is correct |
29 |
Correct |
507 ms |
108120 KB |
Output is correct |
30 |
Correct |
676 ms |
107396 KB |
Output is correct |
31 |
Correct |
464 ms |
110020 KB |
Output is correct |
32 |
Correct |
446 ms |
106292 KB |
Output is correct |
33 |
Correct |
465 ms |
110924 KB |
Output is correct |
34 |
Correct |
633 ms |
112724 KB |
Output is correct |
35 |
Correct |
602 ms |
111176 KB |
Output is correct |
36 |
Correct |
916 ms |
112900 KB |
Output is correct |
37 |
Correct |
637 ms |
114092 KB |
Output is correct |
38 |
Correct |
1075 ms |
113336 KB |
Output is correct |
39 |
Correct |
656 ms |
116728 KB |
Output is correct |
40 |
Correct |
685 ms |
114632 KB |
Output is correct |
41 |
Correct |
666 ms |
114000 KB |
Output is correct |
42 |
Correct |
928 ms |
112268 KB |
Output is correct |
43 |
Correct |
885 ms |
113864 KB |
Output is correct |
44 |
Correct |
737 ms |
114860 KB |
Output is correct |
45 |
Correct |
1140 ms |
112964 KB |
Output is correct |
46 |
Correct |
1125 ms |
108344 KB |
Output is correct |
47 |
Correct |
1029 ms |
105168 KB |
Output is correct |
48 |
Correct |
882 ms |
102304 KB |
Output is correct |
49 |
Correct |
889 ms |
102268 KB |
Output is correct |
50 |
Correct |
808 ms |
110624 KB |
Output is correct |
51 |
Correct |
15 ms |
66392 KB |
Output is correct |
52 |
Correct |
27 ms |
66908 KB |
Output is correct |
53 |
Correct |
666 ms |
111020 KB |
Output is correct |
54 |
Correct |
831 ms |
112660 KB |
Output is correct |
55 |
Correct |
865 ms |
112844 KB |
Output is correct |
56 |
Correct |
868 ms |
115356 KB |
Output is correct |
57 |
Correct |
15 ms |
64344 KB |
Output is correct |
58 |
Correct |
31 ms |
66712 KB |
Output is correct |
59 |
Correct |
708 ms |
110184 KB |
Output is correct |
60 |
Correct |
1075 ms |
111184 KB |
Output is correct |
61 |
Correct |
1027 ms |
110636 KB |
Output is correct |
62 |
Correct |
978 ms |
110716 KB |
Output is correct |
63 |
Correct |
943 ms |
107592 KB |
Output is correct |
64 |
Correct |
1082 ms |
108784 KB |
Output is correct |
65 |
Correct |
1020 ms |
107552 KB |
Output is correct |
66 |
Correct |
526 ms |
111048 KB |
Output is correct |
67 |
Correct |
1006 ms |
110652 KB |
Output is correct |
68 |
Correct |
806 ms |
109904 KB |
Output is correct |
69 |
Correct |
673 ms |
111888 KB |
Output is correct |
70 |
Correct |
783 ms |
109220 KB |
Output is correct |
71 |
Correct |
992 ms |
109800 KB |
Output is correct |