#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000;
vector<int> val, all;
int numval;
struct segtree {
int seg[4 * maxn];
void update(int curin, int curl, int curr, int in, int val) {
if (in < curl || in > curr) return;
if (curl == curr) {
seg[curin] = max(seg[curin], val);
return;
}
update(curin * 2 + 1, curl, (curl + curr) / 2, in, val),
update(curin * 2 + 2, (curl + curr) / 2 + 1, curr, in, val);
seg[curin] = max(seg[curin * 2 + 1], seg[curin * 2 + 2]);
}
int query(int curin, int curl, int curr, int ql, int qr) {
if (ql > curr || qr < curl) return 0;
if (ql <= curl && curr <= qr) return seg[curin];
return max(query(curin * 2 + 1, curl, (curl + curr) / 2, ql, qr),
query(curin * 2 + 2, (curl + curr) / 2 + 1, curr, ql, qr));
}
} up, down;
void init(int N, vector<int> H) {
all = H;
set<int> si;
for (int i = 0; i < N; i++) si.insert(H[i]);
numval = si.size();
for (auto a : si) val.push_back(a);
// for (auto a : val) cout << a << ' ';
// cout << "\n";
}
int max_towers(int L, int R, int D) {
memset(up.seg, 0, sizeof up.seg);
memset(down.seg, 0, sizeof down.seg);
for (int i = L; i <= R; i++) {
int small =
upper_bound(val.begin(), val.end(), all[i] - D) - val.begin() - 1;
int exact = lower_bound(val.begin(), val.end(), all[i]) - val.begin();
int higher = lower_bound(val.begin(), val.end(), all[i] + D) - val.begin();
// cout << i << ' ' << L << ' ' << R << " ";
// cout << small << " " << exact << " " << higher << "\n";
if (small >= 0)
down.update(0, 0, numval - 1, exact,
up.query(0, 0, numval - 1, 0, small));
if (higher >= 0)
up.update(0, 0, numval - 1, exact,
down.query(0, 0, numval - 1, higher, numval - 1) + 1);
// cout << "UP: ";
// for (int i = 0; i < numval; i++)
// cout << up.query(0, 0, numval - 1, i, i) << " ";
// cout << "\nDOWN: ";
// for (int i = 0; i < numval; i++)
// cout << down.query(0, 0, numval - 1, i, i) << " ";
// cout << "\n";
}
return up.query(0, 0, numval - 1, 0, numval - 1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4024 ms |
7144 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3416 KB |
Output is correct |
2 |
Correct |
2 ms |
3672 KB |
Output is correct |
3 |
Correct |
2 ms |
3672 KB |
Output is correct |
4 |
Correct |
2 ms |
3672 KB |
Output is correct |
5 |
Correct |
2 ms |
3672 KB |
Output is correct |
6 |
Correct |
2 ms |
3672 KB |
Output is correct |
7 |
Correct |
2 ms |
3672 KB |
Output is correct |
8 |
Correct |
2 ms |
3672 KB |
Output is correct |
9 |
Correct |
4 ms |
3672 KB |
Output is correct |
10 |
Correct |
2 ms |
3672 KB |
Output is correct |
11 |
Correct |
2 ms |
3672 KB |
Output is correct |
12 |
Correct |
2 ms |
3416 KB |
Output is correct |
13 |
Correct |
2 ms |
3672 KB |
Output is correct |
14 |
Correct |
2 ms |
3672 KB |
Output is correct |
15 |
Correct |
2 ms |
3672 KB |
Output is correct |
16 |
Correct |
3 ms |
3672 KB |
Output is correct |
17 |
Correct |
2 ms |
3672 KB |
Output is correct |
18 |
Correct |
3 ms |
3672 KB |
Output is correct |
19 |
Correct |
2 ms |
3672 KB |
Output is correct |
20 |
Correct |
3 ms |
3672 KB |
Output is correct |
21 |
Correct |
3 ms |
3672 KB |
Output is correct |
22 |
Correct |
3 ms |
3672 KB |
Output is correct |
23 |
Correct |
2 ms |
3664 KB |
Output is correct |
24 |
Correct |
2 ms |
3672 KB |
Output is correct |
25 |
Correct |
2 ms |
3416 KB |
Output is correct |
26 |
Correct |
3 ms |
3672 KB |
Output is correct |
27 |
Correct |
3 ms |
3668 KB |
Output is correct |
28 |
Correct |
3 ms |
3672 KB |
Output is correct |
29 |
Correct |
3 ms |
3672 KB |
Output is correct |
30 |
Correct |
2 ms |
3672 KB |
Output is correct |
31 |
Correct |
3 ms |
3672 KB |
Output is correct |
32 |
Correct |
2 ms |
3672 KB |
Output is correct |
33 |
Correct |
2 ms |
3672 KB |
Output is correct |
34 |
Correct |
2 ms |
3672 KB |
Output is correct |
35 |
Correct |
3 ms |
3672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3416 KB |
Output is correct |
2 |
Correct |
2 ms |
3672 KB |
Output is correct |
3 |
Correct |
2 ms |
3672 KB |
Output is correct |
4 |
Correct |
2 ms |
3672 KB |
Output is correct |
5 |
Correct |
2 ms |
3672 KB |
Output is correct |
6 |
Correct |
2 ms |
3672 KB |
Output is correct |
7 |
Correct |
2 ms |
3672 KB |
Output is correct |
8 |
Correct |
2 ms |
3672 KB |
Output is correct |
9 |
Correct |
4 ms |
3672 KB |
Output is correct |
10 |
Correct |
2 ms |
3672 KB |
Output is correct |
11 |
Correct |
2 ms |
3672 KB |
Output is correct |
12 |
Correct |
2 ms |
3416 KB |
Output is correct |
13 |
Correct |
2 ms |
3672 KB |
Output is correct |
14 |
Correct |
2 ms |
3672 KB |
Output is correct |
15 |
Correct |
2 ms |
3672 KB |
Output is correct |
16 |
Correct |
3 ms |
3672 KB |
Output is correct |
17 |
Correct |
2 ms |
3672 KB |
Output is correct |
18 |
Correct |
3 ms |
3672 KB |
Output is correct |
19 |
Correct |
2 ms |
3672 KB |
Output is correct |
20 |
Correct |
3 ms |
3672 KB |
Output is correct |
21 |
Correct |
3 ms |
3672 KB |
Output is correct |
22 |
Correct |
3 ms |
3672 KB |
Output is correct |
23 |
Correct |
2 ms |
3664 KB |
Output is correct |
24 |
Correct |
2 ms |
3672 KB |
Output is correct |
25 |
Correct |
2 ms |
3416 KB |
Output is correct |
26 |
Correct |
3 ms |
3672 KB |
Output is correct |
27 |
Correct |
3 ms |
3668 KB |
Output is correct |
28 |
Correct |
3 ms |
3672 KB |
Output is correct |
29 |
Correct |
3 ms |
3672 KB |
Output is correct |
30 |
Correct |
2 ms |
3672 KB |
Output is correct |
31 |
Correct |
3 ms |
3672 KB |
Output is correct |
32 |
Correct |
2 ms |
3672 KB |
Output is correct |
33 |
Correct |
2 ms |
3672 KB |
Output is correct |
34 |
Correct |
2 ms |
3672 KB |
Output is correct |
35 |
Correct |
3 ms |
3672 KB |
Output is correct |
36 |
Correct |
39 ms |
7380 KB |
Output is correct |
37 |
Correct |
50 ms |
9524 KB |
Output is correct |
38 |
Correct |
63 ms |
9500 KB |
Output is correct |
39 |
Correct |
46 ms |
9548 KB |
Output is correct |
40 |
Correct |
46 ms |
9336 KB |
Output is correct |
41 |
Correct |
86 ms |
9336 KB |
Output is correct |
42 |
Correct |
49 ms |
9540 KB |
Output is correct |
43 |
Correct |
51 ms |
9520 KB |
Output is correct |
44 |
Correct |
33 ms |
9548 KB |
Output is correct |
45 |
Correct |
27 ms |
9352 KB |
Output is correct |
46 |
Correct |
29 ms |
9540 KB |
Output is correct |
47 |
Correct |
71 ms |
9484 KB |
Output is correct |
48 |
Correct |
65 ms |
9548 KB |
Output is correct |
49 |
Correct |
47 ms |
9540 KB |
Output is correct |
50 |
Correct |
35 ms |
9536 KB |
Output is correct |
51 |
Correct |
40 ms |
9548 KB |
Output is correct |
52 |
Correct |
124 ms |
9440 KB |
Output is correct |
53 |
Correct |
114 ms |
9540 KB |
Output is correct |
54 |
Correct |
115 ms |
9540 KB |
Output is correct |
55 |
Correct |
66 ms |
9540 KB |
Output is correct |
56 |
Correct |
63 ms |
9548 KB |
Output is correct |
57 |
Correct |
87 ms |
9288 KB |
Output is correct |
58 |
Correct |
92 ms |
9540 KB |
Output is correct |
59 |
Correct |
110 ms |
9540 KB |
Output is correct |
60 |
Correct |
122 ms |
9540 KB |
Output is correct |
61 |
Correct |
103 ms |
9540 KB |
Output is correct |
62 |
Correct |
94 ms |
9540 KB |
Output is correct |
63 |
Correct |
105 ms |
9348 KB |
Output is correct |
64 |
Correct |
54 ms |
9548 KB |
Output is correct |
65 |
Correct |
58 ms |
9416 KB |
Output is correct |
66 |
Correct |
56 ms |
9556 KB |
Output is correct |
67 |
Correct |
50 ms |
9548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4035 ms |
9512 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4016 ms |
4952 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3416 KB |
Output is correct |
2 |
Correct |
2 ms |
3672 KB |
Output is correct |
3 |
Correct |
2 ms |
3672 KB |
Output is correct |
4 |
Correct |
2 ms |
3672 KB |
Output is correct |
5 |
Correct |
2 ms |
3672 KB |
Output is correct |
6 |
Correct |
2 ms |
3672 KB |
Output is correct |
7 |
Correct |
2 ms |
3672 KB |
Output is correct |
8 |
Correct |
2 ms |
3672 KB |
Output is correct |
9 |
Correct |
4 ms |
3672 KB |
Output is correct |
10 |
Correct |
2 ms |
3672 KB |
Output is correct |
11 |
Correct |
2 ms |
3672 KB |
Output is correct |
12 |
Correct |
2 ms |
3416 KB |
Output is correct |
13 |
Correct |
2 ms |
3672 KB |
Output is correct |
14 |
Correct |
2 ms |
3672 KB |
Output is correct |
15 |
Correct |
2 ms |
3672 KB |
Output is correct |
16 |
Correct |
3 ms |
3672 KB |
Output is correct |
17 |
Correct |
2 ms |
3672 KB |
Output is correct |
18 |
Correct |
3 ms |
3672 KB |
Output is correct |
19 |
Correct |
2 ms |
3672 KB |
Output is correct |
20 |
Correct |
3 ms |
3672 KB |
Output is correct |
21 |
Correct |
3 ms |
3672 KB |
Output is correct |
22 |
Correct |
3 ms |
3672 KB |
Output is correct |
23 |
Correct |
2 ms |
3664 KB |
Output is correct |
24 |
Correct |
2 ms |
3672 KB |
Output is correct |
25 |
Correct |
2 ms |
3416 KB |
Output is correct |
26 |
Correct |
3 ms |
3672 KB |
Output is correct |
27 |
Correct |
3 ms |
3668 KB |
Output is correct |
28 |
Correct |
3 ms |
3672 KB |
Output is correct |
29 |
Correct |
3 ms |
3672 KB |
Output is correct |
30 |
Correct |
2 ms |
3672 KB |
Output is correct |
31 |
Correct |
3 ms |
3672 KB |
Output is correct |
32 |
Correct |
2 ms |
3672 KB |
Output is correct |
33 |
Correct |
2 ms |
3672 KB |
Output is correct |
34 |
Correct |
2 ms |
3672 KB |
Output is correct |
35 |
Correct |
3 ms |
3672 KB |
Output is correct |
36 |
Correct |
39 ms |
7380 KB |
Output is correct |
37 |
Correct |
50 ms |
9524 KB |
Output is correct |
38 |
Correct |
63 ms |
9500 KB |
Output is correct |
39 |
Correct |
46 ms |
9548 KB |
Output is correct |
40 |
Correct |
46 ms |
9336 KB |
Output is correct |
41 |
Correct |
86 ms |
9336 KB |
Output is correct |
42 |
Correct |
49 ms |
9540 KB |
Output is correct |
43 |
Correct |
51 ms |
9520 KB |
Output is correct |
44 |
Correct |
33 ms |
9548 KB |
Output is correct |
45 |
Correct |
27 ms |
9352 KB |
Output is correct |
46 |
Correct |
29 ms |
9540 KB |
Output is correct |
47 |
Correct |
71 ms |
9484 KB |
Output is correct |
48 |
Correct |
65 ms |
9548 KB |
Output is correct |
49 |
Correct |
47 ms |
9540 KB |
Output is correct |
50 |
Correct |
35 ms |
9536 KB |
Output is correct |
51 |
Correct |
40 ms |
9548 KB |
Output is correct |
52 |
Correct |
124 ms |
9440 KB |
Output is correct |
53 |
Correct |
114 ms |
9540 KB |
Output is correct |
54 |
Correct |
115 ms |
9540 KB |
Output is correct |
55 |
Correct |
66 ms |
9540 KB |
Output is correct |
56 |
Correct |
63 ms |
9548 KB |
Output is correct |
57 |
Correct |
87 ms |
9288 KB |
Output is correct |
58 |
Correct |
92 ms |
9540 KB |
Output is correct |
59 |
Correct |
110 ms |
9540 KB |
Output is correct |
60 |
Correct |
122 ms |
9540 KB |
Output is correct |
61 |
Correct |
103 ms |
9540 KB |
Output is correct |
62 |
Correct |
94 ms |
9540 KB |
Output is correct |
63 |
Correct |
105 ms |
9348 KB |
Output is correct |
64 |
Correct |
54 ms |
9548 KB |
Output is correct |
65 |
Correct |
58 ms |
9416 KB |
Output is correct |
66 |
Correct |
56 ms |
9556 KB |
Output is correct |
67 |
Correct |
50 ms |
9548 KB |
Output is correct |
68 |
Execution timed out |
4035 ms |
9512 KB |
Time limit exceeded |
69 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4024 ms |
7144 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |