#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int L = 22;
int n, a[N], pl[N], pr[N], ord[N];
bool cmp(int i, int j) { return a[i] < a[j]; }
int mx[N][L], logs[N];
int qmx(int l, int r) {
int k = logs[r - l + 1];
return max(mx[l][k], mx[r - (1 << k) + 1][k]);
}
void buildST() {
for (int i = 1; i <= n; i++) mx[i][0] = a[i];
for (int i = 2; i <= n; i++) logs[i] = logs[i >> 1] + 1;
for (int j = 1; j < L; j++)
for (int i = 1; i + (1 << j) <= n + 1; i++)
mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
}
vector<int> qs;
void init(int N, vector<int> H) {
n = N;
for (int i = 1; i <= n; i++) a[i] = H[i - 1];
vector <int> stk;
for (int i = 1; i <= n; i++) {
while (!stk.empty() && a[stk.back()] > a[i]) stk.pop_back();
pl[i] = (stk.empty() ? -1 : stk.back());
stk.push_back(i);
}
stk.clear();
for (int i = n; i >= 1; i--) {
while (!stk.empty() && a[stk.back()] > a[i]) stk.pop_back();
pr[i] = (stk.empty() ? -1 : stk.back());
stk.push_back(i);
}
buildST();
for (int i = 1; i <= n; i++) ord[i] = i;
sort(ord + 1, ord + n + 1, cmp);
for (int _i = 2; _i <= n; _i++) {
int i = ord[_i];
int D = 1e9;
if (pl[i] != -1) D = min(D, qmx(pl[i] + 1, i) - a[i]);
if (pr[i] != -1) D = min(D, qmx(i, pr[i] - 1) - a[i]);
qs.push_back(D);
// printf("i=%d delta->%d\n", i, D);
}
sort(qs.begin(), qs.end());
}
int max_towers(int L, int R, int D) {
int res = 1 + qs.end() - lower_bound(qs.begin(), qs.end(), D);
return res;
}
/*
7 1
10 20 60 40 50 30 70
0 6 17
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
320 ms |
7588 KB |
1st lines differ - on the 1st token, expected: '1', found: '2' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '13', found: '131' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '13', found: '131' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
737 ms |
12192 KB |
1st lines differ - on the 1st token, expected: '11903', found: '33010' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
309 ms |
3168 KB |
Output is correct |
2 |
Correct |
644 ms |
12188 KB |
Output is correct |
3 |
Correct |
808 ms |
12280 KB |
Output is correct |
4 |
Correct |
853 ms |
12280 KB |
Output is correct |
5 |
Correct |
902 ms |
12272 KB |
Output is correct |
6 |
Correct |
663 ms |
12232 KB |
Output is correct |
7 |
Correct |
708 ms |
12192 KB |
Output is correct |
8 |
Correct |
734 ms |
12720 KB |
Output is correct |
9 |
Correct |
804 ms |
12696 KB |
Output is correct |
10 |
Correct |
738 ms |
12700 KB |
Output is correct |
11 |
Correct |
855 ms |
12736 KB |
Output is correct |
12 |
Correct |
48 ms |
12236 KB |
Output is correct |
13 |
Correct |
47 ms |
12192 KB |
Output is correct |
14 |
Correct |
43 ms |
12228 KB |
Output is correct |
15 |
Correct |
30 ms |
12692 KB |
Output is correct |
16 |
Correct |
32 ms |
12452 KB |
Output is correct |
17 |
Correct |
42 ms |
11844 KB |
Output is correct |
18 |
Correct |
43 ms |
12276 KB |
Output is correct |
19 |
Correct |
52 ms |
12228 KB |
Output is correct |
20 |
Correct |
42 ms |
12272 KB |
Output is correct |
21 |
Correct |
43 ms |
12180 KB |
Output is correct |
22 |
Correct |
48 ms |
12312 KB |
Output is correct |
23 |
Correct |
42 ms |
12280 KB |
Output is correct |
24 |
Correct |
30 ms |
12700 KB |
Output is correct |
25 |
Correct |
30 ms |
12720 KB |
Output is correct |
26 |
Correct |
31 ms |
12448 KB |
Output is correct |
27 |
Correct |
29 ms |
12708 KB |
Output is correct |
28 |
Correct |
1 ms |
464 KB |
Output is correct |
29 |
Correct |
1 ms |
464 KB |
Output is correct |
30 |
Correct |
1 ms |
464 KB |
Output is correct |
31 |
Correct |
1 ms |
464 KB |
Output is correct |
32 |
Correct |
1 ms |
464 KB |
Output is correct |
33 |
Correct |
1 ms |
336 KB |
Output is correct |
34 |
Correct |
1 ms |
464 KB |
Output is correct |
35 |
Correct |
1 ms |
464 KB |
Output is correct |
36 |
Correct |
1 ms |
592 KB |
Output is correct |
37 |
Correct |
1 ms |
464 KB |
Output is correct |
38 |
Correct |
1 ms |
464 KB |
Output is correct |
39 |
Correct |
1 ms |
464 KB |
Output is correct |
40 |
Correct |
1 ms |
464 KB |
Output is correct |
41 |
Correct |
1 ms |
464 KB |
Output is correct |
42 |
Correct |
1 ms |
464 KB |
Output is correct |
43 |
Correct |
1 ms |
464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '13', found: '131' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
320 ms |
7588 KB |
1st lines differ - on the 1st token, expected: '1', found: '2' |
2 |
Halted |
0 ms |
0 KB |
- |