#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> pr, h;
const int K = 17;
vector<pair<int, int>> sp[K];
vector<int> spm[K];
vector<int> ds;
inline int msb(int x){
return 31-__builtin_clz(x);
}
int que(int l, int r){
int d = msb(r-l+1);
return max(sp[d][l], sp[d][r-(1<<d)+1]).second;
}
int qum(int l, int r){
int d = msb(r-l+1);
return min(spm[d][l], spm[d][r-(1<<d)+1]);
}
bool sub1 = true;
int th;
void init(int N, std::vector<int> H) {
h = H;
pr.resize(N);
pr[0]=0;
auto mx = max_element(h.begin(), h.end());
if(is_sorted(h.begin(), mx) && is_sorted(mx, h.end(), greater<int>())) {
sub1=true;
th = mx-h.begin();
}
else sub1=false;
int l[N], r[N], p[N];
for(int i = 0;i < K;i++) {
sp[i].resize(N);
spm[i].resize(N);
}
for(int i = 0;i < N;i++){
l[i]=i;
while(l[i]&&H[l[i]-1]<H[i]) l[i]=l[l[i]-1];
sp[0][i] = {H[i], i};spm[0][i]=H[i];
}
for(int i = N-1;i >= 0;i--){
r[i]=i;
while(r[i]<N-1&&H[r[i]+1]<H[i]) r[i]=r[r[i]+1];
if(i==th) continue;
if(!l[i] || (r[i]<N-1&&H[l[i]-1]>H[r[i]+1])){
p[i] = r[i]+1;
} else {
p[i]=l[i]-1;
}
}
vector<pair<int, int>> D;
bool mark[N] = {false};
mark[th] = true;
for(int i = 0;i < N;i++){
if(i==th) continue;
D.push_back({H[p[i]]-qum(l[i], r[i]), i});
}
sort(D.begin(), D.end(), greater<pair<int, int>>());
for(auto [d, i] : D){
mark[i] = true;
if(mark[p[i]]) {
mark[p[i]] = false;
} else ds.push_back(d);
}
for(int k = 1;k < K;k++){
for(int i = 0;i+(1<<k)<=N;i++){
sp[k][i] = max(sp[k-1][i], sp[k-1][i+(1<<k-1)]);
spm[k][i] = min(spm[k-1][i], spm[k-1][i+(1<<k-1)]);
}
}
for(int i = 1;i < N-1;i++){
pr[i]=pr[i-1];
if(H[i] < H[i-1] && H[i] < H[i+1]) pr[i]++;
}
}
int de;
int ans(int l, int r, int atm){
if(l==r){
if(h[l]<=atm) return 1;
return 0;
}
int m = que(l, r);
if(l==m) return ans(l+1, r, atm);
if(m==r) return ans(l, r-1, atm);
return max(ans(l, m-1, h[m]-de)+ans(m+1, r, h[m]-de), (qum(l,r) <= atm ? 1 : 0));
}
int max_towers(int L, int R, int D) {
if(!L && R == h.size()-1){
return 1+lower_bound(ds.begin(), ds.end(), D-1, greater<int>())-ds.begin();
}
if(sub1){
if(L>th || R < th) return 1;
return (h[R] <= h[th]-D && h[L] <= h[th]-D ? 2 : 1);
}
de = D;
if(L+1>=R) return 1;
if(D==1) return pr[R-1]-pr[L]+(h[L] < h[L+1])+(h[R]<h[R-1]);
return ans(L, R, INT_MAX);
}
Compilation message
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:68:49: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
68 | sp[k][i] = max(sp[k-1][i], sp[k-1][i+(1<<k-1)]);
| ~^~
towers.cpp:69:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
69 | spm[k][i] = min(spm[k-1][i], spm[k-1][i+(1<<k-1)]);
| ~^~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:89:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | if(!L && R == h.size()-1){
| ~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
283 ms |
14548 KB |
Output is correct |
2 |
Correct |
645 ms |
24240 KB |
Output is correct |
3 |
Correct |
621 ms |
24248 KB |
Output is correct |
4 |
Correct |
609 ms |
24272 KB |
Output is correct |
5 |
Correct |
593 ms |
24272 KB |
Output is correct |
6 |
Correct |
598 ms |
24272 KB |
Output is correct |
7 |
Correct |
660 ms |
24272 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
856 KB |
Output is correct |
10 |
Correct |
0 ms |
856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
856 KB |
Output is correct |
3 |
Correct |
1 ms |
880 KB |
Output is correct |
4 |
Correct |
1 ms |
856 KB |
Output is correct |
5 |
Correct |
1 ms |
856 KB |
Output is correct |
6 |
Correct |
1 ms |
856 KB |
Output is correct |
7 |
Correct |
1 ms |
856 KB |
Output is correct |
8 |
Correct |
1 ms |
856 KB |
Output is correct |
9 |
Correct |
1 ms |
856 KB |
Output is correct |
10 |
Correct |
1 ms |
856 KB |
Output is correct |
11 |
Correct |
1 ms |
856 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
856 KB |
Output is correct |
14 |
Correct |
1 ms |
856 KB |
Output is correct |
15 |
Correct |
1 ms |
856 KB |
Output is correct |
16 |
Correct |
1 ms |
856 KB |
Output is correct |
17 |
Correct |
1 ms |
1108 KB |
Output is correct |
18 |
Correct |
1 ms |
856 KB |
Output is correct |
19 |
Correct |
1 ms |
856 KB |
Output is correct |
20 |
Correct |
1 ms |
856 KB |
Output is correct |
21 |
Correct |
1 ms |
856 KB |
Output is correct |
22 |
Correct |
1 ms |
856 KB |
Output is correct |
23 |
Correct |
1 ms |
856 KB |
Output is correct |
24 |
Incorrect |
1 ms |
856 KB |
1st lines differ - on the 1st token, expected: '5', found: '6' |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
856 KB |
Output is correct |
3 |
Correct |
1 ms |
880 KB |
Output is correct |
4 |
Correct |
1 ms |
856 KB |
Output is correct |
5 |
Correct |
1 ms |
856 KB |
Output is correct |
6 |
Correct |
1 ms |
856 KB |
Output is correct |
7 |
Correct |
1 ms |
856 KB |
Output is correct |
8 |
Correct |
1 ms |
856 KB |
Output is correct |
9 |
Correct |
1 ms |
856 KB |
Output is correct |
10 |
Correct |
1 ms |
856 KB |
Output is correct |
11 |
Correct |
1 ms |
856 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
856 KB |
Output is correct |
14 |
Correct |
1 ms |
856 KB |
Output is correct |
15 |
Correct |
1 ms |
856 KB |
Output is correct |
16 |
Correct |
1 ms |
856 KB |
Output is correct |
17 |
Correct |
1 ms |
1108 KB |
Output is correct |
18 |
Correct |
1 ms |
856 KB |
Output is correct |
19 |
Correct |
1 ms |
856 KB |
Output is correct |
20 |
Correct |
1 ms |
856 KB |
Output is correct |
21 |
Correct |
1 ms |
856 KB |
Output is correct |
22 |
Correct |
1 ms |
856 KB |
Output is correct |
23 |
Correct |
1 ms |
856 KB |
Output is correct |
24 |
Incorrect |
1 ms |
856 KB |
1st lines differ - on the 1st token, expected: '5', found: '6' |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
444 ms |
24016 KB |
Output is correct |
2 |
Correct |
580 ms |
24264 KB |
Output is correct |
3 |
Correct |
580 ms |
24232 KB |
Output is correct |
4 |
Correct |
557 ms |
24516 KB |
Output is correct |
5 |
Correct |
579 ms |
24516 KB |
Output is correct |
6 |
Correct |
701 ms |
24524 KB |
Output is correct |
7 |
Correct |
617 ms |
24524 KB |
Output is correct |
8 |
Correct |
641 ms |
24272 KB |
Output is correct |
9 |
Correct |
588 ms |
24272 KB |
Output is correct |
10 |
Correct |
624 ms |
24272 KB |
Output is correct |
11 |
Correct |
660 ms |
24272 KB |
Output is correct |
12 |
Correct |
573 ms |
24272 KB |
Output is correct |
13 |
Correct |
636 ms |
24272 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
856 KB |
Output is correct |
16 |
Correct |
1 ms |
856 KB |
Output is correct |
17 |
Correct |
30 ms |
24460 KB |
Output is correct |
18 |
Correct |
29 ms |
24524 KB |
Output is correct |
19 |
Correct |
37 ms |
24524 KB |
Output is correct |
20 |
Correct |
22 ms |
24272 KB |
Output is correct |
21 |
Correct |
27 ms |
24272 KB |
Output is correct |
22 |
Correct |
31 ms |
24272 KB |
Output is correct |
23 |
Correct |
29 ms |
24516 KB |
Output is correct |
24 |
Correct |
30 ms |
24472 KB |
Output is correct |
25 |
Correct |
22 ms |
24272 KB |
Output is correct |
26 |
Incorrect |
35 ms |
24236 KB |
1st lines differ - on the 1st token, expected: '5', found: '6' |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
167 ms |
6232 KB |
1st lines differ - on the 1st token, expected: '7197', found: '7276' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
856 KB |
Output is correct |
3 |
Correct |
1 ms |
880 KB |
Output is correct |
4 |
Correct |
1 ms |
856 KB |
Output is correct |
5 |
Correct |
1 ms |
856 KB |
Output is correct |
6 |
Correct |
1 ms |
856 KB |
Output is correct |
7 |
Correct |
1 ms |
856 KB |
Output is correct |
8 |
Correct |
1 ms |
856 KB |
Output is correct |
9 |
Correct |
1 ms |
856 KB |
Output is correct |
10 |
Correct |
1 ms |
856 KB |
Output is correct |
11 |
Correct |
1 ms |
856 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
856 KB |
Output is correct |
14 |
Correct |
1 ms |
856 KB |
Output is correct |
15 |
Correct |
1 ms |
856 KB |
Output is correct |
16 |
Correct |
1 ms |
856 KB |
Output is correct |
17 |
Correct |
1 ms |
1108 KB |
Output is correct |
18 |
Correct |
1 ms |
856 KB |
Output is correct |
19 |
Correct |
1 ms |
856 KB |
Output is correct |
20 |
Correct |
1 ms |
856 KB |
Output is correct |
21 |
Correct |
1 ms |
856 KB |
Output is correct |
22 |
Correct |
1 ms |
856 KB |
Output is correct |
23 |
Correct |
1 ms |
856 KB |
Output is correct |
24 |
Incorrect |
1 ms |
856 KB |
1st lines differ - on the 1st token, expected: '5', found: '6' |
25 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
283 ms |
14548 KB |
Output is correct |
2 |
Correct |
645 ms |
24240 KB |
Output is correct |
3 |
Correct |
621 ms |
24248 KB |
Output is correct |
4 |
Correct |
609 ms |
24272 KB |
Output is correct |
5 |
Correct |
593 ms |
24272 KB |
Output is correct |
6 |
Correct |
598 ms |
24272 KB |
Output is correct |
7 |
Correct |
660 ms |
24272 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
856 KB |
Output is correct |
10 |
Correct |
0 ms |
856 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
856 KB |
Output is correct |
13 |
Correct |
1 ms |
880 KB |
Output is correct |
14 |
Correct |
1 ms |
856 KB |
Output is correct |
15 |
Correct |
1 ms |
856 KB |
Output is correct |
16 |
Correct |
1 ms |
856 KB |
Output is correct |
17 |
Correct |
1 ms |
856 KB |
Output is correct |
18 |
Correct |
1 ms |
856 KB |
Output is correct |
19 |
Correct |
1 ms |
856 KB |
Output is correct |
20 |
Correct |
1 ms |
856 KB |
Output is correct |
21 |
Correct |
1 ms |
856 KB |
Output is correct |
22 |
Correct |
0 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
856 KB |
Output is correct |
24 |
Correct |
1 ms |
856 KB |
Output is correct |
25 |
Correct |
1 ms |
856 KB |
Output is correct |
26 |
Correct |
1 ms |
856 KB |
Output is correct |
27 |
Correct |
1 ms |
1108 KB |
Output is correct |
28 |
Correct |
1 ms |
856 KB |
Output is correct |
29 |
Correct |
1 ms |
856 KB |
Output is correct |
30 |
Correct |
1 ms |
856 KB |
Output is correct |
31 |
Correct |
1 ms |
856 KB |
Output is correct |
32 |
Correct |
1 ms |
856 KB |
Output is correct |
33 |
Correct |
1 ms |
856 KB |
Output is correct |
34 |
Incorrect |
1 ms |
856 KB |
1st lines differ - on the 1st token, expected: '5', found: '6' |
35 |
Halted |
0 ms |
0 KB |
- |