#include "towers.h"
#include <cassert>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> h;
struct segtree{
int sz;
vector<int> tree;
void init(int n, vector<int> a) {
sz = 1;
while (sz < n)
sz *= 2;
tree.assign(sz * 2, 0);
for (int i = 0; i < n; ++i) {
tree[i + sz] = a[i];
}
for (int i = sz - 1; i > 0; --i) {
tree[i] = tree[i * 2] + tree[i * 2 + 1];
}
}
int get(int l, int r) {
int res = 0;
while (l <= r) {
if (l & 1) {
res += tree[l];
l++;
}
if ((r & 1) == 0) {
res += tree[r];
r--;
}
l /= 2;r /= 2;
}
return res;
}
};
segtree sg;
void init(int n, vector<int> hh) {
h = hh;
vector<int> bebra(n);
for (int i = 1; i + 1 < n; ++i) {
if (hh[i-1] > hh[i] and hh[i] < hh[i + 1])
bebra[i] = 1;
}
sg.init(n, bebra);
}
int max_towers(int L, int R, int D) {
if (D == 1) {
int val = sg.get(L + 1, R - 1);
if (L + 1 <= R and h[L] < h[L + 1])
val++;
if (L + 1 <= R and h[R-1] > h[R])
val++;
return max(val, 1);
}
vector<int> dp(h.size(), 1);
int res = 0;
for (int i = L; i < R; ++i) {
int mx = h[i];
res = max(res, dp[i]);
for (int j = i + 1; j <= R; ++j) {
mx = max(mx, h[j]);
if (mx - D >= max(h[i], h[j]) and h[j - 1] > h[j] and (j == R or h[j + 1] > h[j])) {
dp[j] = max(dp[j], dp[i] + 1);
}
}
}
res = max(res, dp[R]);
return res;
}
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
/usr/bin/ld: /tmp/ccvsh300.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccGkx1V1.o:towers.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
