#include <bits/stdc++.h>
#include "towers.h"
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
using namespace std;
ll powmod(ll base,ll exponent,ll mod){
ll ans=1;
if(base<0) base+=mod;
while(exponent){
if(exponent&1)ans=(ans*base)%mod;
base=(base*base)%mod;
exponent/=2;
}
return ans;
}
ll gcd(ll a, ll b){
if(b==0) return a;
else return gcd(b,a%b);
}
const int INF = 1e9;
const ll INFLL = 4e18;
const int upperlimit = 1e5+1;
const int mod = 1e9+7;
struct info{
int diff,len[2],start[2],end[2];
};
bool operator < (const info &a,const info &b){return(a.diff < b.diff);}
vector<info> segtree[4*upperlimit];
info merge(int differ, info <,info &rt){
info ans;
ans.diff = differ;
if(lt.len[0]&1){
if(lt.end[0] + differ <= rt.start[1]){
ans.len[0] = lt.len[0] + rt.len[1];
ans.start[0] = lt.start[0];
ans.end[0] = rt.end[1];
}
else{
ans.len[0] = lt.len[0] + rt.len[0] - 1;
if(lt.len[0] == 1) ans.start[0] = min(lt.start[0],rt.start[0]);
else ans.start[0] = lt.start[0];
if(rt.len[0] == 1) ans.end[0] = min(lt.end[0],rt.end[0]);
else ans.end[0] = rt.end[0];
}
}
else{
if(lt.end[0] - differ >= rt.start[0]){
ans.len[0] = lt.len[0] + rt.len[0];
ans.start[0] = lt.start[0];
ans.end[0] = rt.end[0];
}
else{
ans.len[0] = lt.len[0] + rt.len[1] - 1;
ans.start[0] = lt.start[0];
if(rt.len[1] == 1) ans.end[0] = max(lt.end[0],rt.end[1]);
else ans.end[0] = rt.end[1];
}
}
if(lt.len[1]&1){
if(lt.end[1] - differ >= rt.start[0]){
ans.len[1] = lt.len[1] + rt.len[0];
ans.start[1] = lt.start[0];
ans.end[1] = rt.end[0];
}
else{
ans.len[1] = lt.len[1] + rt.len[1] - 1;
if(lt.len[1] == 1) ans.start[1] = max(lt.start[1],rt.start[1]);
else ans.start[1] = lt.start[1];
if(rt.len[1] == 1) ans.end[1] = max(lt.end[1],rt.end[1]);
else ans.end[1] = rt.end[1];
}
}
else{
if(lt.end[1] + differ <= rt.start[1]){
ans.len[1] = lt.len[1] + rt.len[1];
ans.start[1] = lt.start[1];
ans.end[1] = rt.end[1];
}
else{
ans.len[1] = lt.len[1] + rt.len[0] - 1;
ans.start[1] = lt.start[1];
if(rt.len[0] == 1) ans.end[1] = min(lt.end[1],rt.end[0]);
else ans.end[1] = rt.end[0];
}
}
return ans;
}
void calculate_node(int &par){
int lt = par<<1;
int rt = (par<<1)+1;
int p1 = 0, p2 = 0,prev = 0;
while((p1 < segtree[lt].size()) && (p2 < segtree[rt].size())){
info temp;
if(segtree[lt][p1].diff == INF && segtree[rt][p2].diff == INF){
int gg = max(segtree[rt][p2].start[1],segtree[lt][p1].start[1]) - min(segtree[lt][p1].start[0],segtree[rt][p2].start[0]);
if(gg > prev) segtree[par].pb(merge(gg,segtree[lt][p1],segtree[rt][p2]));
}
prev = min(segtree[lt][p1].diff,segtree[rt][p2].diff);
segtree[par].pb(merge(prev,segtree[lt][p1],segtree[rt][p2]));
if(segtree[lt][p1].diff < segtree[rt][p2].diff) p1++;
else if(segtree[lt][p1].diff > segtree[rt][p2].diff) p2++;
else{
p1++;
p2++;
}
}
}
void build(int node,int i,int j, vi &h){
if(i==j){
info temp;
temp.start[0] = temp.start[1] = temp.end[0] = temp.end[1] = h[i];
temp.len[0] = temp.len[1] = 1;
temp.diff = INF;
segtree[node].pb(temp);
return;
}
int mid = (i+j)>>1;
build(node<<1,i,mid,h);build((node<<1)+1,mid+1,j,h);
calculate_node(node);
}
void query_nodes(int node,int i,int j,int &l,int &r, vi &node_list){
if((i > r) || (l > j) || (i > j) || (l > r)) return;
if((i >= l) && (j <= r)){ node_list.pb(node); return; }
int mid = (i+j)>>1;
query_nodes(node<<1,i,mid,l,r,node_list);
query_nodes((node<<1)+1,mid+1,j,l,r,node_list);
}
int n;
vi h;
void init(int N, vi H){
n = N;
h = H;
build(1,0,n-1,H);
}
int max_towers(int L, int R, int D){
vi node_list;
info ans;
ans.diff = D;
ans.len[0] = ans.len[1] = 1;
ans.start[0] = ans.start[1] = ans.end[0] = ans.end[1] = h[L];
L++;
query_nodes(1,0,n-1,L,R,node_list);
for(int node : node_list){
auto it = lower_bound(segtree[node].begin(), segtree[node].end(),ans);
ans = merge(D,ans,*it);
}
return ((ans.len[0]+1)/2);
}
int main(){
int N,Q,L,R,D;
cin >> N >> Q;
vi H(N);
for(int &i : H) cin >> i;
init(N,H);
while(Q--){
cin >> L >> R >> D;
cout << max_towers(L,R,D) << endl;
}
return 0;
}
Compilation message
towers.cpp: In function 'void calculate_node(int&)':
towers.cpp:110:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | while((p1 < segtree[lt].size()) && (p2 < segtree[rt].size())){
| ~~~^~~~~~~~~~~~~~~~~~~~
towers.cpp:110:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | while((p1 < segtree[lt].size()) && (p2 < segtree[rt].size())){
| ~~~^~~~~~~~~~~~~~~~~~~~
towers.cpp:111:8: warning: unused variable 'temp' [-Wunused-variable]
111 | info temp;
| ^~~~
/usr/bin/ld: /tmp/ccVdOd9F.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccsc01JE.o:towers.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
