#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
const int inf = 1e9 + 10;
int v[maxn];
bool resp[maxn], active[maxn];
struct query{
int l, r, k, id, maxi = -inf;
query( int l = 0, int r = 0, int k = 0, int id = 0) : l(l), r(r), k(k), id(id) {}
};
vector<query> q1, q2, queries;
bool cmp1( query a, query b ){
return a.l > b.l;
}
bool cmp2( query a, query b ){
return a.r < b.r;
}
void calcula( int ini, int fim, vector<query>& left, vector<query>& right ){
if( ini >= fim ) return;
int mid = ( ini + fim )/2;
// cout << " ---------- " << ini << " " << fim << " " << mid << endl;
int pl = 0, pr = 0;
int maxi = -inf, maxi2 = -inf, maxsum = -inf;
// cout << "l: ";
// for( query cur : left ) cout << cur.l << " ";
// cout << endl;
// cout << "r: ";
// for( query cur : right ) cout << cur.r << " ";
// cout << endl;
while( pl < left.size() && left[pl].l > mid ) pl++;
while( pr < right.size() && right[pr].r <= mid ) pr++;
// cout << pl << " " << pr << "----" << endl;
for( int i = mid; i >= ini; i-- ){
if( v[i] > maxi ){
swap( maxi, maxi2 );
maxi = v[i];
maxsum = maxi + maxi2;
}
else if( v[i] > maxi2 ){
maxi2 = v[i];
maxsum = maxi + maxi2;
}
while( pl < left.size() && left[pl].l <= i ){
if( queries[ left[pl].id ].r < mid ){ pl++; continue; }
if( left[pl].k < maxsum ) resp[ left[pl].id ] = false;
queries[ left[pl].id ].maxi = maxi;
// cout << "-> " << left[pl].id << " " << resp[ left[pl].id ] << endl;
pl++;
}
}
// cout << "---" << endl;
set<int> s;
maxi = -inf, maxi2 = -inf, maxsum = -inf;
for( int i = mid + 1; i <= fim; i++ ){
s.insert(v[i]);
if( v[i] > maxi ){
maxi = v[i];
maxi2 = -inf;
}
else if( v[i] > maxi2 ){
maxi2 = v[i];
maxsum = max( maxsum, maxi + maxi2 );
}
while( pr < right.size() && right[pr].r == i ){
if( queries[ right[pr].id ].l > mid ){ pr++; continue; }
if( right[pr].k < maxsum ) resp[ right[pr].id ] = false;
auto it = s.lower_bound( queries[ right[pr].id ].maxi );
if( it != s.begin() ){
it--;
if( right[pr].k < queries[ right[pr].id ].maxi + *it ) resp[ right[pr].id ] = false;
}
queries[ right[pr].id ].maxi = -inf;
// cout << "-> " << right[pr].id << " " << resp[ right[pr].id ] << endl;
pr++;
}
}
vector<query> l1, l2, r1, r2;
for( query cur : left ){
if( cur.l < mid ) l1.push_back( cur );
else if( cur.l > mid ) l2.push_back( cur );
}
for( query cur : right ){
if( queries[ cur.id ].l < mid ){
queries[cur.id].r = min( mid - 1, queries[cur.id].r );
cur.r = min( mid - 1, cur.r );
r1.push_back( cur );
}
else if( queries[ cur.id ].l > mid ) r2.push_back( cur );
}
calcula( ini, mid - 1, l1, r1 );
calcula( mid + 1, fim, l2, r2 );
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m; cin >> n >> m;
queries.emplace_back();
for( int i = 1; i <= n; i++ ) cin >> v[i];
for( int i = 1; i <= m; i++ ){
int l, r, k; cin >> l >> r >> k;
resp[i] = true;
q1.push_back( query( l, r, k, i ) );
q2.push_back( query( l, r, k, i ) );
queries.push_back( query( l, r, k, i ) );
}
sort( q1.begin(), q1.end(), cmp1 );
sort( q2.begin(), q2.end(), cmp2 );
calcula( 1, n, q1, q2 );
for( int i = 1; i <= m; i++ ) cout << resp[i] << "\n";
}
Compilation message
sortbooks.cpp: In function 'void calcula(int, int, std::vector<query>&, std::vector<query>&)':
sortbooks.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | while( pl < left.size() && left[pl].l > mid ) pl++;
| ~~~^~~~~~~~~~~~~
sortbooks.cpp:47:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | while( pr < right.size() && right[pr].r <= mid ) pr++;
| ~~~^~~~~~~~~~~~~~
sortbooks.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | while( pl < left.size() && left[pl].l <= i ){
| ~~~^~~~~~~~~~~~~
sortbooks.cpp:91:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | while( pr < right.size() && right[pr].r == i ){
| ~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3080 ms |
222744 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
223 ms |
15744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
