#include <bits/stdc++.h>
using namespace std;
const int C = 8;
vector<int>w;
vector<int>st;
vector<vector<int>>v;
void dbg(vector<int>c) {
for(auto z : c)
cout << z << " ";
cout << "\n\n";
}
void build(int i_, int j_, int p_) {
if(i_ == j_) {
st[p_] = 0;
v[p_].push_back(w[i_]);
return;
}
int mid_ = (i_ + j_) >> 1;
build(i_, mid_, 2 * p_);
build(mid_ + 1, j_, 2 * p_ + 1);
int mx = max(st[2 * p_], st[2 * p_ + 1]);
int p = 0;
const int MAX = (v[2 * p_].empty() ? 0 : v[2 * p_].back());
for(int i = 0 ; i < (int)v[2 * p_].size() ; i++) {
while(p < (int)v[2 * p_ + 1].size() && v[2 * p_ + 1][p] < v[2 * p_][i]) {
v[p_].push_back(v[2 * p_ + 1][p]);
mx = max(mx, MAX + v[p_].back());
p++;
}
v[p_].push_back(v[2 * p_][i]);
}
while(p < (int)v[2 * p_ + 1].size())
v[p_].push_back(v[2 * p_ + 1][p]), p++;
st[p_] = mx;
}
int l_, r_;
int ans;
vector<int>query(int i_, int j_, int p_) {
if(i_ > r_ || j_ < l_)
return {};
if(i_ >= l_ && j_ <= r_) {
ans = max(ans, st[p_]);
return v[p_];
}
int mid_ = (i_ + j_) >> 1;
vector<int>v1 = query(i_, mid_, 2 * p_),
v2 = query(mid_ + 1, j_, 2 * p_ + 1),
v3;
int p = 0;
const int MAX = (v1.empty() ? 0 : v1.back());
for(int i = 0 ; i < (int)v1.size() ; i++) {
while(p < (int)v2.size() && v2[p] < v1[i]) {
v3.push_back(v2[p]);
ans = max(ans, MAX + v3.back()));
p++;
}
v3.push_back(v1[i]);
}
while(p < (int)v2.size())
v3.push_back(v2[p++]);
return v3;
}
signed main() {
int N,Q;
scanf("%d%d", &N, &Q);
w.resize(N);
st.resize(C * N);
v.resize(C * N);
for(auto &in : w)
scanf("%d", &in);
build(0, N-1, 1);
while(Q--) {
int l,r,k;
scanf("%d%d%d", &l, &r, &k);
l--,r--;
l_ = l, r_ = r, ans = 0;
auto x = query(0, N-1, 1);
cout << (ans <= k) << "\n";
}
return 0;
}
Compilation message
sortbooks.cpp: In function 'std::vector<int> query(int, int, int)':
sortbooks.cpp:60:44: error: expected ';' before ')' token
60 | ans = max(ans, MAX + v3.back()));
| ^
| ;
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d%d", &N, &Q);
| ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | scanf("%d", &in);
| ~~~~~^~~~~~~~~~~
sortbooks.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%d%d%d", &l, &r, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
