#include <bits/stdc++.h>
#define MAX_N 1000000
using namespace std;
int w[MAX_N];
int lower( vector <int> &v, int x ) {
int l, r, mid;
l = 0;
r = v.size();
while ( r - l > 1 ) {
mid = (l + r) / 2;
if ( v[mid] < x )
l = mid;
else
r = mid;
}
return v[l] < x ? v[l] : -x;
}
struct nod {
int maxEffort, maxW;
vector <int> v;
};
struct answer {
int maxEfort, maxW;
};
nod aint[4 * MAX_N];
answer ans;
void init( int nod, int l, int r ) {
int mid, i, j;
if ( l == r ) {
aint[nod].maxEffort = 0;
aint[nod].maxW = w[l];
aint[nod].v.push_back( w[l] );
return;
}
mid = (l + r) / 2;
init( nod * 2 + 1, l, mid );
init( nod * 2 + 2, mid + 1, r );
aint[nod].maxW = max( aint[nod * 2 + 1].maxW, aint[nod * 2 + 2].maxW );
aint[nod].maxEffort = max( max( aint[nod * 2 + 1].maxEffort, aint[nod * 2 + 2].maxEffort ), aint[nod * 2 + 1].maxW + lower( aint[nod * 2 + 2].v, aint[nod * 2 + 1].maxW ) );
i = j = 0;
while ( i < aint[nod * 2 + 1].v.size() && j < aint[nod * 2 + 2].v.size() ) {
if ( aint[nod * 2 + 1].v[i] < aint[nod * 2 + 2].v[j] ) {
aint[nod].v.push_back( aint[nod * 2 + 1].v[i] );
i++;
} else {
aint[nod].v.push_back( aint[nod * 2 + 2].v[j] );
j++;
}
}
while ( i < aint[nod * 2 + 1].v.size() ) {
aint[nod].v.push_back( aint[nod * 2 + 1].v[i] );
i++;
}
while ( j < aint[nod * 2 + 2].v.size() ) {
aint[nod].v.push_back( aint[nod * 2 + 2].v[j] );
j++;
}
}
void query( int nod, int l, int r, int lq, int rq ) {
int mid;
if ( nod == 0 )
ans = { 0, 0 };
if ( l > rq || r < lq )
return;
if ( lq <= l && r <= rq ) {
ans.maxEfort = max( max( ans.maxEfort, aint[nod].maxEffort ), ans.maxW + lower( aint[nod].v, ans.maxW ) );
ans.maxW = max( ans.maxW, aint[nod].maxW );
return;
}
mid = (l + r) / 2;
query( nod * 2 + 1, l, mid, lq, rq );
query( nod * 2 + 2, mid + 1, r, lq, rq );
}
};
signed main() {
int n, m, l, r, k, i;
cin >> n >> m;
for ( i = 0; i < n; i++ )
cin >> w[i];
init( 0, 0, n - 1 );
for ( i = 0; i < m; i++ ) {
cin >> l >> r >> k;
query( 0, 0, n - 1, l - 1, r - 1 );
if ( ans.maxEfort > k )
cout << "0\n";
else
cout << "1\n";
}
return 0;
}
Compilation message
sortbooks.cpp: In function 'void init(int, int, int)':
sortbooks.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | while ( i < aint[nod * 2 + 1].v.size() && j < aint[nod * 2 + 2].v.size() ) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:57:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | while ( i < aint[nod * 2 + 1].v.size() && j < aint[nod * 2 + 2].v.size() ) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | while ( i < aint[nod * 2 + 1].v.size() ) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | while ( j < aint[nod * 2 + 2].v.size() ) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp: At global scope:
sortbooks.cpp:95:1: error: expected declaration before '}' token
95 | };
| ^
