#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+3, maxm = 2e5+3, maxw = 1e9+3;
int n, m;
int w[maxn];
int mxsum[4*maxn];
set<int> els[4*maxn];
void build(int l, int r, int v) {
if (l == r) {
mxsum[v] = -1;
els[v].insert(-w[l]);
} else {
int mid = (l+r)/2;
build(l, mid, v*2);
build(mid+1, r, v*2+1);
auto it = els[v*2+1].upper_bound(*els[v*2].begin());
mxsum[v] = max({mxsum[v*2], mxsum[v*2+1], (it == els[v*2+1].end() ? -1 : -*els[v*2].begin() - *it)});
for (int x : els[v*2]) els[v].insert(x);
for (int x : els[v*2+1]) els[v].insert(x);
}
}
int query2(int l, int r, int v, int lb, int rb) {
if (r < lb || l > rb) return -1;
if (l >= lb && r <= rb) return -*els[v].begin();
int mid = (l+r)/2;
return max(query2(l, mid, v*2, lb, rb), query2(mid+1, r, v*2+1, lb, rb));
}
int query3(int l, int r, int v, int lb, int rb, int k) {
if (r < lb || l > rb) return -1;
if (l >= lb && r <= rb) {
auto it = els[v].upper_bound(-k);
return (it == els[v].end() ? -1 : -*it);
}
int mid = (l+r)/2;
return max(query3(l, mid, v*2, lb, rb, k), query3(mid+1, r, v*2+1, lb, rb, k));
}
int query1(int l, int r, int v, int lb, int rb) {
if (r < lb || l > rb) return -1;
if (l >= lb && r <= rb) return mxsum[v];
int mid = (l+r)/2;
int mxl = -1, mxr = -1;
mxl = query2(l, mid, v*2, lb, mid);
if (mxl != -1) mxr = query3(mid+1, r, v*2+1, mid+1, rb, mxl);
return max({
query1(l, mid, v*2, lb, rb),
query1(mid+1, r, v*2+1, lb, rb),
(mxr == -1 ? -1 : mxl + mxr)
});
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
if (n <= maxn) {
for (int i=0; i<n; i++) cin >> w[i];
build(0, n-1, 1);
// for (int i=0; i<n; i++) {
// for (int j=i; j<n; j++) {
// cout << i << ' ' << j << ' ' << query1(0, n-1, 1, i, j) << '\n';
// }
// }
while (m--) {
int l, r, k;
cin >> l >> r >> k;
else cout << (query1(0, n-1, 1, l-1, r-1) <= k) << '\n';
}
} else {
for (int i=0; i<n; i++) cin >> w[0];
while (m--) {
int l, r, k;
cin >> l >> r >> k;
cout << (l == r) << '\n';
}
}
return 0;
}
Compilation message
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:74:4: error: 'else' without a previous 'if'
74 | else cout << (query1(0, n-1, 1, l-1, r-1) <= k) << '\n';
| ^~~~
