#include "towers.h"
#include <bits/stdc++.h>
using std::vector;
using std::string;
using std::cin;
using std::cout;
using ll = int;
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;
ll D;
vi right, left;
constexpr ll di = 21;
ll sz;
vii pr, mr, pl, ml;
vii sum;
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];
D = -1;
}
int max_towers(int L, int R, int d) {
if(D == -1){
D = d;
{
sz = N/di+10;
sum.resize(sz, vi(sz));
pr.resize(N+2);
mr.resize(N+2);
pl.resize(N+2);
ml.resize(N+2);
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]+D)-vmi.begin();
large = imi[large];
ll small = lower_bound(all(vma),H[i])-vma.begin()-1;
small = ima[small];
if(small >= large) left[i] = small+1;
else left[i] = -1;
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]+D)-vmi.begin();
large = imi[large];
ll small = lower_bound(all(vma),H[i])-vma.begin()-1;
small = ima[small];
if(small <= large) right[i] = small-1;
else right[i] = N;
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){
left[i]++;
right[i]++;
ll ld = (left[i]+di-1)/di;
ll rd = right[i]/di;
sum[ld][rd]++;
ll id = i/di;
sum[ld][id]--;
id = (i+2+di-1)/di;
sum[id][rd]--;
pr[right[i]].pb(left[i]);
pl[left[i]].pb(right[i]);
ml[i+2].pb(right[i]);
ml[left[i]].pb(i);
mr[i].pb(left[i]);
mr[right[i]].pb(i+2);
}
per(l,sz,0){
rep(i,0,sz){
ll j = i+l;
if(j >= sz) break;
if(i) sum[i][j] += sum[i-1][j];
if(j+1 < sz) sum[i][j] += sum[i][j+1];
if(i && j+1<sz) sum[i][j] -= sum[i-1][j+1];
}
}
rep(i,0,N+2){
sort(all(pr[i]));
sort(all(pl[i]));
sort(all(mr[i]));
sort(all(ml[i]));
}
}
ll ans = 0;
L++, R++;
ll ld = L/di;
ll rd = (R+di-1)/di;
ans = sum[ld][rd];
REP(i, ld*di+1, L){
ans += pl[i].end()-lower_bound(all(pl[i]), R);
ans -= ml[i].end()-lower_bound(all(ml[i]), R);
}
rep(i,R,rd*di){
if(i >= pr[i].size()) continue;
ans += upper_bound(all(pr[i]), ld*di)-pr[i].begin();
ans -= upper_bound(all(mr[i]), ld*di)-mr[i].begin();
}
return ans;
}
Compilation message
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:146:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | if(i >= pr[i].size()) continue;
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
365 ms |
44780 KB |
31st lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
336 KB |
1st lines differ - on the 1st token, expected: '13', found: '19' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
336 KB |
1st lines differ - on the 1st token, expected: '13', found: '19' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
806 ms |
109376 KB |
2nd lines differ - on the 1st token, expected: '4770', found: '4777' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
21180 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
336 KB |
1st lines differ - on the 1st token, expected: '13', found: '19' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
365 ms |
44780 KB |
31st lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
