#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<<31)-1;
ll N;
vi H;
ll D;
vi right, left;
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;
{
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);
}
}
}
else return 0;
ll ans = 0;
REP(idx,L,R){
if(left[idx] <= L && R <= right[idx]) ans++;
}
return ans;
}
Compilation message
towers.cpp:20:27: warning: integer overflow in expression of type 'int' results in '2147483647' [-Woverflow]
20 | constexpr ll inf = (1<<31)-1;
| ~~~~~~~^~
towers.cpp:20:28: error: overflow in constant expression [-fpermissive]
20 | constexpr ll inf = (1<<31)-1;
| ^
towers.cpp:20:28: error: overflow in constant expression [-fpermissive]
