// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
template<class T> using V = vector<T>;
using vi = V<int>;
struct Seg {
const int ID = 0; int cmb(int a, int b) { return a + b; };
vi seg, lazy; int N; void init(int n) {
for(N = 1; N < n; N *= 2);
seg.assign(2 * N, 0); lazy.assign(2 * N, -1);
}
void pull(int x) { seg[x] = cmb(seg[2*x], seg[2*x+1]); }
void push(int x, int L, int R) {
if (lazy[x] != -1) {
seg[x] = (R-L+1) * lazy[x];
if (L != R) for(int i = 0; i < 2; i++) lazy[2*x+i] = lazy[x];
lazy[x] = -1;
}
}
void upd(int l, int r, int v, int x, int L, int R) {
push(x, L, R); if (R < l || r < L) return;
if (l <= L && R <= r) {
lazy[x] = v; push(x, L, R); return;
}
int M = (L + R) / 2;
upd(l, r, v, 2 * x, L, M);
upd(l, r, v, 2 * x + 1, M + 1, R);
pull(x);
}
int query(int l, int r, int x, int L, int R) {
push(x, L, R); if (R < l || r < L) return ID;
if (l <= L && R <= r) return seg[x];
int M = (L + R) / 2;
return cmb(query(l, r, 2 * x, L, M), query(l, r, 2 * x + 1, M + 1, R));
}
void upd(int l, int r, int v) { upd(l, r, v, 1, 0, N - 1); }
int qry(int l, int r) { return query(l, r, 1, 0, N - 1); }
};
const int LG = 19;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N; cin >> N;
vi L(N), R(N); for(int i = 0; i < N; i++) cin >> L[i] >> R[i];
int M = -1;
{
map<int, int> mp; int cur = 0;
for(auto& x : L) mp[x]++;
for(auto& x : R) mp[x]++;
for(auto& x : mp) x.second = cur++;
for(auto& x : L) x = mp[x];
for(auto& x : R) x = mp[x];
M = cur;
}
Seg st; st.init(M);
V<vi> nxt(N + 1, vi(LG, N)); int bnd = 0;
for(int i = 0; i < N; i++) {
// cout << i << " ==> " << L[i] << " " << R[i] << endl;
while(bnd < N && !st.qry(L[bnd], R[bnd])) {
st.upd(L[bnd], R[bnd], 1);
bnd++;
}
nxt[i][0] = bnd;
// cout << i << " => " << bnd << endl;
st.upd(L[i], R[i], 0);
}
for(int x = N - 1; x >= 0; x--) {
for(int i = 1; i < LG; i++) nxt[x][i] = nxt[nxt[x][i-1]][i-1];
}
int Q; cin >> Q;
for(int q = 0; q < Q; q++) {
int l, r; cin >> l >> r; --l, --r;
int ans = 0;
for(int i = LG - 1; i >= 0; i--) {
if (nxt[l][i] <= r) { ans += (1 << i); l = nxt[l][i]; }
}
cout << ans + 1 << nl;
}
exit(0-0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
732 ms |
36376 KB |
Output is correct |
2 |
Correct |
694 ms |
36052 KB |
Output is correct |
3 |
Correct |
659 ms |
35956 KB |
Output is correct |
4 |
Correct |
693 ms |
36192 KB |
Output is correct |
5 |
Correct |
731 ms |
37456 KB |
Output is correct |
6 |
Correct |
60 ms |
26688 KB |
Output is correct |
7 |
Correct |
65 ms |
27124 KB |
Output is correct |
8 |
Correct |
74 ms |
27212 KB |
Output is correct |
9 |
Correct |
98 ms |
27988 KB |
Output is correct |
10 |
Correct |
92 ms |
26888 KB |
Output is correct |
11 |
Correct |
453 ms |
36572 KB |
Output is correct |
12 |
Correct |
438 ms |
34780 KB |
Output is correct |
13 |
Correct |
427 ms |
34380 KB |
Output is correct |
14 |
Correct |
491 ms |
36376 KB |
Output is correct |
15 |
Correct |
470 ms |
35496 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
60 ms |
28448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
1372 KB |
Output is correct |
2 |
Correct |
11 ms |
1372 KB |
Output is correct |
3 |
Correct |
11 ms |
1372 KB |
Output is correct |
4 |
Correct |
11 ms |
1372 KB |
Output is correct |
5 |
Correct |
11 ms |
1420 KB |
Output is correct |
6 |
Correct |
4 ms |
1116 KB |
Output is correct |
7 |
Correct |
4 ms |
1172 KB |
Output is correct |
8 |
Correct |
4 ms |
1116 KB |
Output is correct |
9 |
Correct |
4 ms |
1116 KB |
Output is correct |
10 |
Correct |
4 ms |
1116 KB |
Output is correct |
11 |
Correct |
7 ms |
1376 KB |
Output is correct |
12 |
Correct |
7 ms |
1372 KB |
Output is correct |
13 |
Correct |
7 ms |
1372 KB |
Output is correct |
14 |
Correct |
8 ms |
1372 KB |
Output is correct |
15 |
Correct |
8 ms |
1232 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
3 ms |
1128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
1372 KB |
Output is correct |
2 |
Correct |
11 ms |
1372 KB |
Output is correct |
3 |
Correct |
11 ms |
1372 KB |
Output is correct |
4 |
Correct |
11 ms |
1372 KB |
Output is correct |
5 |
Correct |
11 ms |
1420 KB |
Output is correct |
6 |
Correct |
4 ms |
1116 KB |
Output is correct |
7 |
Correct |
4 ms |
1172 KB |
Output is correct |
8 |
Correct |
4 ms |
1116 KB |
Output is correct |
9 |
Correct |
4 ms |
1116 KB |
Output is correct |
10 |
Correct |
4 ms |
1116 KB |
Output is correct |
11 |
Correct |
7 ms |
1376 KB |
Output is correct |
12 |
Correct |
7 ms |
1372 KB |
Output is correct |
13 |
Correct |
7 ms |
1372 KB |
Output is correct |
14 |
Correct |
8 ms |
1372 KB |
Output is correct |
15 |
Correct |
8 ms |
1232 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
3 ms |
1128 KB |
Output is correct |
18 |
Correct |
70 ms |
4132 KB |
Output is correct |
19 |
Correct |
68 ms |
3652 KB |
Output is correct |
20 |
Correct |
71 ms |
3924 KB |
Output is correct |
21 |
Correct |
67 ms |
3828 KB |
Output is correct |
22 |
Correct |
84 ms |
3884 KB |
Output is correct |
23 |
Correct |
57 ms |
3416 KB |
Output is correct |
24 |
Correct |
60 ms |
3672 KB |
Output is correct |
25 |
Correct |
62 ms |
3692 KB |
Output is correct |
26 |
Correct |
64 ms |
3716 KB |
Output is correct |
27 |
Correct |
58 ms |
3712 KB |
Output is correct |
28 |
Correct |
41 ms |
3340 KB |
Output is correct |
29 |
Correct |
45 ms |
3408 KB |
Output is correct |
30 |
Correct |
43 ms |
3568 KB |
Output is correct |
31 |
Correct |
44 ms |
3332 KB |
Output is correct |
32 |
Correct |
45 ms |
3416 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
42 ms |
3452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
719 ms |
37556 KB |
Output is correct |
2 |
Correct |
775 ms |
37184 KB |
Output is correct |
3 |
Correct |
622 ms |
35104 KB |
Output is correct |
4 |
Correct |
606 ms |
34744 KB |
Output is correct |
5 |
Correct |
724 ms |
35524 KB |
Output is correct |
6 |
Correct |
60 ms |
26888 KB |
Output is correct |
7 |
Correct |
64 ms |
26572 KB |
Output is correct |
8 |
Correct |
70 ms |
26820 KB |
Output is correct |
9 |
Correct |
93 ms |
26496 KB |
Output is correct |
10 |
Correct |
97 ms |
28692 KB |
Output is correct |
11 |
Correct |
458 ms |
34396 KB |
Output is correct |
12 |
Correct |
441 ms |
36980 KB |
Output is correct |
13 |
Correct |
430 ms |
34240 KB |
Output is correct |
14 |
Correct |
505 ms |
35200 KB |
Output is correct |
15 |
Correct |
500 ms |
36796 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
59 ms |
27276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
732 ms |
36376 KB |
Output is correct |
2 |
Correct |
694 ms |
36052 KB |
Output is correct |
3 |
Correct |
659 ms |
35956 KB |
Output is correct |
4 |
Correct |
693 ms |
36192 KB |
Output is correct |
5 |
Correct |
731 ms |
37456 KB |
Output is correct |
6 |
Correct |
60 ms |
26688 KB |
Output is correct |
7 |
Correct |
65 ms |
27124 KB |
Output is correct |
8 |
Correct |
74 ms |
27212 KB |
Output is correct |
9 |
Correct |
98 ms |
27988 KB |
Output is correct |
10 |
Correct |
92 ms |
26888 KB |
Output is correct |
11 |
Correct |
453 ms |
36572 KB |
Output is correct |
12 |
Correct |
438 ms |
34780 KB |
Output is correct |
13 |
Correct |
427 ms |
34380 KB |
Output is correct |
14 |
Correct |
491 ms |
36376 KB |
Output is correct |
15 |
Correct |
470 ms |
35496 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
60 ms |
28448 KB |
Output is correct |
18 |
Correct |
12 ms |
1372 KB |
Output is correct |
19 |
Correct |
11 ms |
1372 KB |
Output is correct |
20 |
Correct |
11 ms |
1372 KB |
Output is correct |
21 |
Correct |
11 ms |
1372 KB |
Output is correct |
22 |
Correct |
11 ms |
1420 KB |
Output is correct |
23 |
Correct |
4 ms |
1116 KB |
Output is correct |
24 |
Correct |
4 ms |
1172 KB |
Output is correct |
25 |
Correct |
4 ms |
1116 KB |
Output is correct |
26 |
Correct |
4 ms |
1116 KB |
Output is correct |
27 |
Correct |
4 ms |
1116 KB |
Output is correct |
28 |
Correct |
7 ms |
1376 KB |
Output is correct |
29 |
Correct |
7 ms |
1372 KB |
Output is correct |
30 |
Correct |
7 ms |
1372 KB |
Output is correct |
31 |
Correct |
8 ms |
1372 KB |
Output is correct |
32 |
Correct |
8 ms |
1232 KB |
Output is correct |
33 |
Correct |
0 ms |
348 KB |
Output is correct |
34 |
Correct |
3 ms |
1128 KB |
Output is correct |
35 |
Correct |
70 ms |
4132 KB |
Output is correct |
36 |
Correct |
68 ms |
3652 KB |
Output is correct |
37 |
Correct |
71 ms |
3924 KB |
Output is correct |
38 |
Correct |
67 ms |
3828 KB |
Output is correct |
39 |
Correct |
84 ms |
3884 KB |
Output is correct |
40 |
Correct |
57 ms |
3416 KB |
Output is correct |
41 |
Correct |
60 ms |
3672 KB |
Output is correct |
42 |
Correct |
62 ms |
3692 KB |
Output is correct |
43 |
Correct |
64 ms |
3716 KB |
Output is correct |
44 |
Correct |
58 ms |
3712 KB |
Output is correct |
45 |
Correct |
41 ms |
3340 KB |
Output is correct |
46 |
Correct |
45 ms |
3408 KB |
Output is correct |
47 |
Correct |
43 ms |
3568 KB |
Output is correct |
48 |
Correct |
44 ms |
3332 KB |
Output is correct |
49 |
Correct |
45 ms |
3416 KB |
Output is correct |
50 |
Correct |
0 ms |
348 KB |
Output is correct |
51 |
Correct |
42 ms |
3452 KB |
Output is correct |
52 |
Correct |
719 ms |
37556 KB |
Output is correct |
53 |
Correct |
775 ms |
37184 KB |
Output is correct |
54 |
Correct |
622 ms |
35104 KB |
Output is correct |
55 |
Correct |
606 ms |
34744 KB |
Output is correct |
56 |
Correct |
724 ms |
35524 KB |
Output is correct |
57 |
Correct |
60 ms |
26888 KB |
Output is correct |
58 |
Correct |
64 ms |
26572 KB |
Output is correct |
59 |
Correct |
70 ms |
26820 KB |
Output is correct |
60 |
Correct |
93 ms |
26496 KB |
Output is correct |
61 |
Correct |
97 ms |
28692 KB |
Output is correct |
62 |
Correct |
458 ms |
34396 KB |
Output is correct |
63 |
Correct |
441 ms |
36980 KB |
Output is correct |
64 |
Correct |
430 ms |
34240 KB |
Output is correct |
65 |
Correct |
505 ms |
35200 KB |
Output is correct |
66 |
Correct |
500 ms |
36796 KB |
Output is correct |
67 |
Correct |
0 ms |
348 KB |
Output is correct |
68 |
Correct |
59 ms |
27276 KB |
Output is correct |
69 |
Correct |
824 ms |
38872 KB |
Output is correct |
70 |
Correct |
943 ms |
40576 KB |
Output is correct |
71 |
Correct |
903 ms |
37976 KB |
Output is correct |
72 |
Correct |
832 ms |
39560 KB |
Output is correct |
73 |
Correct |
845 ms |
39068 KB |
Output is correct |
74 |
Correct |
297 ms |
32540 KB |
Output is correct |
75 |
Correct |
256 ms |
30496 KB |
Output is correct |
76 |
Correct |
261 ms |
32796 KB |
Output is correct |
77 |
Correct |
272 ms |
30108 KB |
Output is correct |
78 |
Correct |
256 ms |
30800 KB |
Output is correct |
79 |
Correct |
556 ms |
39608 KB |
Output is correct |
80 |
Correct |
534 ms |
37240 KB |
Output is correct |
81 |
Correct |
546 ms |
37064 KB |
Output is correct |
82 |
Correct |
593 ms |
38600 KB |
Output is correct |
83 |
Correct |
486 ms |
37220 KB |
Output is correct |
84 |
Correct |
0 ms |
348 KB |
Output is correct |
85 |
Correct |
119 ms |
30284 KB |
Output is correct |