#include "towers.h"
#include <bits/stdc++.h>
using std::vector;
using std::string;
using std::cin;
using std::cout;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define ln "\n"
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(), a.end()
#define mp std::make_pair
#define pb emplace_back
constexpr ll inf = (1<<30)+(1<<29)+(1<<28);
ll N;
vi H;
vi right, left;
vi safe;
void init(int n, std::vector<int> h) {
N = n;
H.resize(N);
right.resize(N);
left.resize(N);
rep(i,0,N) H[i] = h[i];
}
int max_towers(int L, int R, int D) {
if(safe.empty()){
rep(i,0,N) left[i] = -inf, right[i] = inf;
while(true){
vi mid(N);
vi flag(N);
bool fff = true;
rep(i,0,N){
if(left[i]+1 < right[i]){
mid[i] = (left[i]+right[i])/2;
flag[i] = true;
fff = false;
}
}
if(fff) break;
{
std::deque<ll> ima, vma, imi, vmi;
ima.pb(-3);
vma.pb(-inf);
imi.pb(-2);
vmi.pb(inf);
rep(i,0,N){
ll large = lower_bound(all(vmi), H[i]+mid[i])-vmi.begin();
large = imi[large];
ll small = lower_bound(all(vma),H[i])-vma.begin()-1;
small = ima[small];
if(small >= large) flag[i] = false;
while(true){
if(vma[vma.size()-1] > H[i]) vma.pop_back(), ima.pop_back();
else break;
}
vma.pb(H[i]);
ima.pb(i);
while(true){
if(vmi[0] < H[i]) vmi.pop_front(), imi.pop_front();
else break;
}
vmi.emplace_front(H[i]);
imi.emplace_front(i);
}
}
{
std::deque<ll> ima, vma, imi, vmi;
ima.pb(N+3);
vma.pb(-inf);
imi.pb(N+2);
vmi.pb(inf);
per(i,N-1,0){
ll large = lower_bound(all(vmi), H[i]+mid[i])-vmi.begin();
large = imi[large];
ll small = lower_bound(all(vma),H[i])-vma.begin()-1;
small = ima[small];
if(small <= large) flag[i] = false;
while(true){
if(vma[vma.size()-1] > H[i]) vma.pop_back(), ima.pop_back();
else break;
}
vma.pb(H[i]);
ima.pb(i);
while(true){
if(vmi[0] < H[i]) vmi.pop_front(), imi.pop_front();
else break;
}
vmi.emplace_front(H[i]);
imi.emplace_front(i);
}
}
rep(i,0,N){
if(left[i]+1 < right[i]){
if(flag[i]) left[i] = mid[i];
else right[i] = mid[i];
}
}
}
safe = left;
sort(all(safe));
}
ll ans = safe.end()-lower_bound(all(safe), D);
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
720 ms |
3764 KB |
1st lines differ - on the 1st token, expected: '1', found: '2' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
208 KB |
1st lines differ - on the 1st token, expected: '13', found: '131' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
208 KB |
1st lines differ - on the 1st token, expected: '13', found: '131' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
691 ms |
4648 KB |
1st lines differ - on the 1st token, expected: '11903', found: '33010' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
347 ms |
1360 KB |
Output is correct |
2 |
Correct |
952 ms |
4604 KB |
Output is correct |
3 |
Correct |
1068 ms |
4604 KB |
Output is correct |
4 |
Correct |
1065 ms |
4728 KB |
Output is correct |
5 |
Correct |
1049 ms |
4608 KB |
Output is correct |
6 |
Correct |
1083 ms |
4592 KB |
Output is correct |
7 |
Correct |
1083 ms |
4620 KB |
Output is correct |
8 |
Correct |
1174 ms |
6252 KB |
Output is correct |
9 |
Correct |
1358 ms |
6264 KB |
Output is correct |
10 |
Correct |
894 ms |
5900 KB |
Output is correct |
11 |
Correct |
1145 ms |
5980 KB |
Output is correct |
12 |
Correct |
407 ms |
4640 KB |
Output is correct |
13 |
Correct |
403 ms |
4700 KB |
Output is correct |
14 |
Correct |
396 ms |
4612 KB |
Output is correct |
15 |
Correct |
603 ms |
6264 KB |
Output is correct |
16 |
Correct |
549 ms |
6100 KB |
Output is correct |
17 |
Correct |
416 ms |
4456 KB |
Output is correct |
18 |
Correct |
397 ms |
4600 KB |
Output is correct |
19 |
Correct |
399 ms |
4604 KB |
Output is correct |
20 |
Correct |
381 ms |
4824 KB |
Output is correct |
21 |
Correct |
376 ms |
4620 KB |
Output is correct |
22 |
Correct |
385 ms |
4812 KB |
Output is correct |
23 |
Correct |
384 ms |
4604 KB |
Output is correct |
24 |
Correct |
613 ms |
6256 KB |
Output is correct |
25 |
Correct |
566 ms |
6332 KB |
Output is correct |
26 |
Correct |
512 ms |
5656 KB |
Output is correct |
27 |
Correct |
557 ms |
6172 KB |
Output is correct |
28 |
Correct |
8 ms |
336 KB |
Output is correct |
29 |
Correct |
8 ms |
384 KB |
Output is correct |
30 |
Correct |
8 ms |
388 KB |
Output is correct |
31 |
Correct |
9 ms |
416 KB |
Output is correct |
32 |
Correct |
10 ms |
404 KB |
Output is correct |
33 |
Correct |
5 ms |
208 KB |
Output is correct |
34 |
Correct |
8 ms |
388 KB |
Output is correct |
35 |
Correct |
8 ms |
380 KB |
Output is correct |
36 |
Correct |
8 ms |
388 KB |
Output is correct |
37 |
Correct |
8 ms |
336 KB |
Output is correct |
38 |
Correct |
8 ms |
336 KB |
Output is correct |
39 |
Correct |
8 ms |
380 KB |
Output is correct |
40 |
Correct |
10 ms |
416 KB |
Output is correct |
41 |
Correct |
9 ms |
412 KB |
Output is correct |
42 |
Correct |
10 ms |
404 KB |
Output is correct |
43 |
Correct |
8 ms |
288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
208 KB |
1st lines differ - on the 1st token, expected: '13', found: '131' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
720 ms |
3764 KB |
1st lines differ - on the 1st token, expected: '1', found: '2' |
2 |
Halted |
0 ms |
0 KB |
- |