#include <bits/stdc++.h>
using namespace std;
const int lg = 16;
int N;
vector<int> H;
struct SparseTable{
static pair<int, int> op(pair<int, int> a, pair<int, int> b){
return {std::min(a.first, b.first), std::max(a.second, b.second)};
}
vector<vector<pair<int, int>>> table;
SparseTable(){}
SparseTable(int N, vector<int> H): table(lg + 1, vector<pair<int, int>>(N)){
for(int i = 0; i < N; i++) table[0][i] = {H[i], H[i]};
for(int l = 1; l <= lg; l++) for(int i = 0; i + (1 << l) <= N; i++){
table[l][i] = op(table[l - 1][i], table[l - 1][i + (1 << l - 1)]);
}
}
pair<int, int> get(int L, int R) const {
const int l = __lg(R - L);
return op(table[l][L], table[l][R - (1 << l)]);
}
} st;
vector<vector<array<array<int, 3>, 2>>> table;
bool first = 1;
void init(int N, vector<int> H) {
::N = N;
::H = H;
st = SparseTable(N, H);
}
void init2(int D) {
first = 0;
table.assign(lg + 1, vector<array<array<int, 3>, 2>>(N));
for(int i = 0; i < N; i++){
int ok = i + 1, ng = N + 1;
auto check = [&](pair<int, int> x){
return H[i] < x.first && x.second < H[i] + D;
};
while(ng - ok > 1){
const int mid = (ok + ng) / 2;
(check(st.get(i + 1, mid)) ? ok : ng) = mid;
}
if(ok == N) table[0][i][0] = {N, 0, 0};
if(H[ok] < H[i]) table[0][i][0] = {ok, 0, 0};
else{
// assert(H[ok] >= H[i] + D);
table[0][i][0] = {ok, 1, 0};
}
}
for(int i = 0; i < N; i++){
int ok = i + 1, ng = N + 1;
auto check = [&](pair<int, int> x){
return H[i] - D < x.first && x.second < H[i];
};
while(ng - ok > 1){
const int mid = (ok + ng) / 2;
(check(st.get(i + 1, mid)) ? ok : ng) = mid;
}
if(ok == N) table[0][i][1] = {N, 1, 0};
if(H[ok] > H[i]) table[0][i][1] = {ok, 1, 0};
else{
// assert(H[ok] <= H[i] - D);
table[0][i][1] = {ok, 0, 1};
}
}
for(int l = 0; l < lg; l++) for(int i = 0; i < N; i++) for(int s = 0; s < 2; s++){
auto [i2, s2, c2] = table[l][i][s];
if(i2 == N){
table[l + 1][i][s] = {i2, s2, c2};
continue;
}
auto [i3, s3, c3] = table[l][i2][s2];
table[l + 1][i][s] = {i3, s3, c2 + c3};
}
}
int max_towers(int L, int R, int D) {
if(first) init2(D);
int i = L, s = 0, c = 1;
for(int l = lg; l >= 0; l--){
auto [i2, s2, c2] = table[l][i][s];
if(i2 > R) continue;
tie(i, s, c) = tuple{i2, s2, c + c2};
}
return c;
}
int main() {
int N, Q;
assert(2 == scanf("%d %d", &N, &Q));
std::vector<int> H(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &H[i]));
}
init(N, H);
for (int i = 0; i < Q; ++i) {
int L, R, D;
assert(3 == scanf("%d %d %d", &L, &R, &D));
printf("%d\n", max_towers(L, R, D));
}
return 0;
}
Compilation message
towers.cpp: In constructor 'SparseTable::SparseTable(int, std::vector<int>)':
towers.cpp:17:72: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
17 | table[l][i] = op(table[l - 1][i], table[l - 1][i + (1 << l - 1)]);
| ~~^~~
/usr/bin/ld: /tmp/cc9LwGAW.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccLNShIT.o:towers.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
