#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 2e5+5;
int n, mx[(1 << 20)], a[N], sp[N][18];
multiset<int, greater<>> val[N+N];
void mxupd(int l, int r, int x, int i, int v) {
if (l == r) {
mx[x] = v;
return;
}
int m = (l + r) >> 1;
if (i <= m)mxupd(l, m, x*2+1, i, v);
else mxupd(m+1, r, x*2+2, i, v);
mx[x] = max(mx[x*2+1], mx[x*2+2]);
}
int mxget(int li, int ri, int x, int l, int r) {
if (li > r || ri < l)return 0;
if (li >= l && ri <= r)return mx[x];
int m = (li + ri) >> 1;
return max(mxget(li, m, x*2+1, l, r), mxget(m+1, ri, x*2+2, l, r));
}
int l[N], r[N];
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
set<int> st;
for (int i = 1; i <= n; i++) {
cin >> l[i] >> r[i];
val[i].insert(0);
val[n+i].insert(0);
st.insert(l[i]), st.insert(r[i]);
}
int cur = 1;
map<int, int> mp;
for (auto &x : st) {
mp[x] = cur++;
}
for (int i = 1; i <= n; i++) {
l[i] = mp[l[i]], r[i] = mp[r[i]];
}
int cr = n;
a[n] = n;
val[l[n]].insert(r[n]);
mxupd(1, 2*n, 0, l[n], r[n]);
for (int cl = n-1; cl >= 1; cl--) {
while (mxget(1, 2*n, 0, 1, r[cl]) >= l[cl]) {
val[l[cr]].erase(val[l[cr]].find(r[cr]));
mxupd(1, 2*n, 0, l[cr], *val[l[cr]].begin());
cr--;
}
val[l[cl]].insert(r[cl]);
mxupd(1, 2*n, 0, l[cl], *val[l[cl]].begin());
a[cl] = cr;
}
for (int i = 1; i <= n; i++) {
sp[i][0] = a[i];
}
for (int j = 1; j < 18; j++) {
for (int i = 1; i <= n; i++) {
if (sp[i][j-1] < n)sp[i][j] = sp[sp[i][j-1] + 1][j-1];
else sp[i][j] = n;
}
}
a[0] = -1;
int q;
cin >> q;
while (q--) {
int a, b;
cin >> a >> b;
int ans = 1;
for (int i = 17; i >= 0 && a < n; i--) {
if (sp[a][i] < b) {
ans += (1 << i);
a = sp[a][i] + 1;
}
}
cout << ans << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
697 ms |
93540 KB |
Output is correct |
2 |
Correct |
632 ms |
96268 KB |
Output is correct |
3 |
Correct |
786 ms |
96584 KB |
Output is correct |
4 |
Correct |
686 ms |
97440 KB |
Output is correct |
5 |
Correct |
686 ms |
99752 KB |
Output is correct |
6 |
Correct |
119 ms |
59984 KB |
Output is correct |
7 |
Correct |
134 ms |
60492 KB |
Output is correct |
8 |
Correct |
129 ms |
60500 KB |
Output is correct |
9 |
Correct |
134 ms |
59092 KB |
Output is correct |
10 |
Correct |
131 ms |
58200 KB |
Output is correct |
11 |
Correct |
560 ms |
107240 KB |
Output is correct |
12 |
Correct |
470 ms |
102996 KB |
Output is correct |
13 |
Correct |
486 ms |
102916 KB |
Output is correct |
14 |
Correct |
629 ms |
103464 KB |
Output is correct |
15 |
Correct |
564 ms |
100692 KB |
Output is correct |
16 |
Correct |
4 ms |
25084 KB |
Output is correct |
17 |
Correct |
126 ms |
61440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
28504 KB |
Output is correct |
2 |
Correct |
15 ms |
26460 KB |
Output is correct |
3 |
Correct |
12 ms |
26456 KB |
Output is correct |
4 |
Correct |
12 ms |
26460 KB |
Output is correct |
5 |
Correct |
13 ms |
26516 KB |
Output is correct |
6 |
Correct |
10 ms |
27740 KB |
Output is correct |
7 |
Correct |
8 ms |
25692 KB |
Output is correct |
8 |
Correct |
9 ms |
27740 KB |
Output is correct |
9 |
Correct |
8 ms |
25688 KB |
Output is correct |
10 |
Correct |
8 ms |
25692 KB |
Output is correct |
11 |
Correct |
12 ms |
28892 KB |
Output is correct |
12 |
Correct |
11 ms |
26712 KB |
Output is correct |
13 |
Correct |
11 ms |
26712 KB |
Output is correct |
14 |
Correct |
13 ms |
28508 KB |
Output is correct |
15 |
Correct |
12 ms |
28508 KB |
Output is correct |
16 |
Correct |
4 ms |
25328 KB |
Output is correct |
17 |
Correct |
8 ms |
25692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
28504 KB |
Output is correct |
2 |
Correct |
15 ms |
26460 KB |
Output is correct |
3 |
Correct |
12 ms |
26456 KB |
Output is correct |
4 |
Correct |
12 ms |
26460 KB |
Output is correct |
5 |
Correct |
13 ms |
26516 KB |
Output is correct |
6 |
Correct |
10 ms |
27740 KB |
Output is correct |
7 |
Correct |
8 ms |
25692 KB |
Output is correct |
8 |
Correct |
9 ms |
27740 KB |
Output is correct |
9 |
Correct |
8 ms |
25688 KB |
Output is correct |
10 |
Correct |
8 ms |
25692 KB |
Output is correct |
11 |
Correct |
12 ms |
28892 KB |
Output is correct |
12 |
Correct |
11 ms |
26712 KB |
Output is correct |
13 |
Correct |
11 ms |
26712 KB |
Output is correct |
14 |
Correct |
13 ms |
28508 KB |
Output is correct |
15 |
Correct |
12 ms |
28508 KB |
Output is correct |
16 |
Correct |
4 ms |
25328 KB |
Output is correct |
17 |
Correct |
8 ms |
25692 KB |
Output is correct |
18 |
Correct |
65 ms |
29164 KB |
Output is correct |
19 |
Correct |
59 ms |
28936 KB |
Output is correct |
20 |
Correct |
65 ms |
31316 KB |
Output is correct |
21 |
Correct |
58 ms |
28752 KB |
Output is correct |
22 |
Correct |
60 ms |
29008 KB |
Output is correct |
23 |
Correct |
54 ms |
27988 KB |
Output is correct |
24 |
Correct |
56 ms |
28268 KB |
Output is correct |
25 |
Correct |
57 ms |
28240 KB |
Output is correct |
26 |
Correct |
59 ms |
28356 KB |
Output is correct |
27 |
Correct |
51 ms |
27956 KB |
Output is correct |
28 |
Correct |
44 ms |
28752 KB |
Output is correct |
29 |
Correct |
47 ms |
28696 KB |
Output is correct |
30 |
Correct |
49 ms |
28924 KB |
Output is correct |
31 |
Correct |
46 ms |
28496 KB |
Output is correct |
32 |
Correct |
52 ms |
30776 KB |
Output is correct |
33 |
Correct |
4 ms |
24920 KB |
Output is correct |
34 |
Correct |
48 ms |
27860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
732 ms |
96020 KB |
Output is correct |
2 |
Correct |
684 ms |
98828 KB |
Output is correct |
3 |
Correct |
648 ms |
94544 KB |
Output is correct |
4 |
Correct |
612 ms |
94036 KB |
Output is correct |
5 |
Correct |
677 ms |
95572 KB |
Output is correct |
6 |
Correct |
125 ms |
60500 KB |
Output is correct |
7 |
Correct |
125 ms |
59968 KB |
Output is correct |
8 |
Correct |
130 ms |
59988 KB |
Output is correct |
9 |
Correct |
126 ms |
59980 KB |
Output is correct |
10 |
Correct |
145 ms |
61816 KB |
Output is correct |
11 |
Correct |
488 ms |
102400 KB |
Output is correct |
12 |
Correct |
568 ms |
108520 KB |
Output is correct |
13 |
Correct |
470 ms |
102628 KB |
Output is correct |
14 |
Correct |
544 ms |
99864 KB |
Output is correct |
15 |
Correct |
624 ms |
104168 KB |
Output is correct |
16 |
Correct |
5 ms |
24924 KB |
Output is correct |
17 |
Correct |
123 ms |
60584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
697 ms |
93540 KB |
Output is correct |
2 |
Correct |
632 ms |
96268 KB |
Output is correct |
3 |
Correct |
786 ms |
96584 KB |
Output is correct |
4 |
Correct |
686 ms |
97440 KB |
Output is correct |
5 |
Correct |
686 ms |
99752 KB |
Output is correct |
6 |
Correct |
119 ms |
59984 KB |
Output is correct |
7 |
Correct |
134 ms |
60492 KB |
Output is correct |
8 |
Correct |
129 ms |
60500 KB |
Output is correct |
9 |
Correct |
134 ms |
59092 KB |
Output is correct |
10 |
Correct |
131 ms |
58200 KB |
Output is correct |
11 |
Correct |
560 ms |
107240 KB |
Output is correct |
12 |
Correct |
470 ms |
102996 KB |
Output is correct |
13 |
Correct |
486 ms |
102916 KB |
Output is correct |
14 |
Correct |
629 ms |
103464 KB |
Output is correct |
15 |
Correct |
564 ms |
100692 KB |
Output is correct |
16 |
Correct |
4 ms |
25084 KB |
Output is correct |
17 |
Correct |
126 ms |
61440 KB |
Output is correct |
18 |
Correct |
14 ms |
28504 KB |
Output is correct |
19 |
Correct |
15 ms |
26460 KB |
Output is correct |
20 |
Correct |
12 ms |
26456 KB |
Output is correct |
21 |
Correct |
12 ms |
26460 KB |
Output is correct |
22 |
Correct |
13 ms |
26516 KB |
Output is correct |
23 |
Correct |
10 ms |
27740 KB |
Output is correct |
24 |
Correct |
8 ms |
25692 KB |
Output is correct |
25 |
Correct |
9 ms |
27740 KB |
Output is correct |
26 |
Correct |
8 ms |
25688 KB |
Output is correct |
27 |
Correct |
8 ms |
25692 KB |
Output is correct |
28 |
Correct |
12 ms |
28892 KB |
Output is correct |
29 |
Correct |
11 ms |
26712 KB |
Output is correct |
30 |
Correct |
11 ms |
26712 KB |
Output is correct |
31 |
Correct |
13 ms |
28508 KB |
Output is correct |
32 |
Correct |
12 ms |
28508 KB |
Output is correct |
33 |
Correct |
4 ms |
25328 KB |
Output is correct |
34 |
Correct |
8 ms |
25692 KB |
Output is correct |
35 |
Correct |
65 ms |
29164 KB |
Output is correct |
36 |
Correct |
59 ms |
28936 KB |
Output is correct |
37 |
Correct |
65 ms |
31316 KB |
Output is correct |
38 |
Correct |
58 ms |
28752 KB |
Output is correct |
39 |
Correct |
60 ms |
29008 KB |
Output is correct |
40 |
Correct |
54 ms |
27988 KB |
Output is correct |
41 |
Correct |
56 ms |
28268 KB |
Output is correct |
42 |
Correct |
57 ms |
28240 KB |
Output is correct |
43 |
Correct |
59 ms |
28356 KB |
Output is correct |
44 |
Correct |
51 ms |
27956 KB |
Output is correct |
45 |
Correct |
44 ms |
28752 KB |
Output is correct |
46 |
Correct |
47 ms |
28696 KB |
Output is correct |
47 |
Correct |
49 ms |
28924 KB |
Output is correct |
48 |
Correct |
46 ms |
28496 KB |
Output is correct |
49 |
Correct |
52 ms |
30776 KB |
Output is correct |
50 |
Correct |
4 ms |
24920 KB |
Output is correct |
51 |
Correct |
48 ms |
27860 KB |
Output is correct |
52 |
Correct |
732 ms |
96020 KB |
Output is correct |
53 |
Correct |
684 ms |
98828 KB |
Output is correct |
54 |
Correct |
648 ms |
94544 KB |
Output is correct |
55 |
Correct |
612 ms |
94036 KB |
Output is correct |
56 |
Correct |
677 ms |
95572 KB |
Output is correct |
57 |
Correct |
125 ms |
60500 KB |
Output is correct |
58 |
Correct |
125 ms |
59968 KB |
Output is correct |
59 |
Correct |
130 ms |
59988 KB |
Output is correct |
60 |
Correct |
126 ms |
59980 KB |
Output is correct |
61 |
Correct |
145 ms |
61816 KB |
Output is correct |
62 |
Correct |
488 ms |
102400 KB |
Output is correct |
63 |
Correct |
568 ms |
108520 KB |
Output is correct |
64 |
Correct |
470 ms |
102628 KB |
Output is correct |
65 |
Correct |
544 ms |
99864 KB |
Output is correct |
66 |
Correct |
624 ms |
104168 KB |
Output is correct |
67 |
Correct |
5 ms |
24924 KB |
Output is correct |
68 |
Correct |
123 ms |
60584 KB |
Output is correct |
69 |
Correct |
807 ms |
99288 KB |
Output is correct |
70 |
Correct |
756 ms |
102680 KB |
Output is correct |
71 |
Correct |
693 ms |
97400 KB |
Output is correct |
72 |
Correct |
777 ms |
100644 KB |
Output is correct |
73 |
Correct |
742 ms |
99660 KB |
Output is correct |
74 |
Correct |
213 ms |
65520 KB |
Output is correct |
75 |
Correct |
199 ms |
63832 KB |
Output is correct |
76 |
Correct |
215 ms |
65616 KB |
Output is correct |
77 |
Correct |
236 ms |
61616 KB |
Output is correct |
78 |
Correct |
231 ms |
64092 KB |
Output is correct |
79 |
Correct |
574 ms |
111392 KB |
Output is correct |
80 |
Correct |
576 ms |
105780 KB |
Output is correct |
81 |
Correct |
529 ms |
105540 KB |
Output is correct |
82 |
Correct |
609 ms |
104084 KB |
Output is correct |
83 |
Correct |
599 ms |
101200 KB |
Output is correct |
84 |
Correct |
5 ms |
24920 KB |
Output is correct |
85 |
Correct |
173 ms |
63740 KB |
Output is correct |