#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
using namespace std;
const long long oo = 1000000000000000000;
long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;
/*
ViHHiPuh
(( `'-""``""-'` ))
)-__-_.._-__-(
/ --- (o _ o) --- \
\ .-* ( .0. ) *-. /
_'-. ,_ '=' _, .-'_
/ `;#'#'# - #'#'#;` \
\_)) -----'#'----- ((_/
# --------- #
'# ------- ------ #'
/..-'# ------- #'-.\
_\...-\'# -- #'/-.../_
((____)- '#' -(____))
cout << fixed << setprecision(6) << x;
freopen ( "sum.in", "r", stdin )
*/
struct Node {
vector <int> v;
int ans;
public :
Node operator + ( Node a ) {
Node c;
c.ans = max( ans, a.ans );
int l, r;
l = r = 0;
int mx = v.back();
int mxx = -1;
while ( l < v.size() && r < a.v.size() ) {
if ( v[ l ] < a.v[ r ] ) {
c.v.push_back( v[ l ] );
l ++;
}
else {
c.v.push_back( a.v[ r ] );
if ( a.v[ r ] > mxx && a.v[ r ] < mx )
mxx = a.v[ r ];
r ++;
}
}
while ( l < v.size() ) {
c.v.push_back( v[ l ] );
l ++;
}
while ( r < a.v.size() ) {
c.v.push_back( a.v[ r ] );
if ( a.v[ r ] > mxx && a.v[ r ] < mx )
mxx = a.v[ r ];
r ++;
}
if ( ~mxx )
c.ans = max( c.ans, mx + mxx );
return c;
}
} t[ 4000001 ];
struct Node1 {
int ans, mx;
} an;
int n, m, a[ 1000001 ];
void build( int v, int tl, int tr ) {
if ( tl == tr ) {
t[ v ].v.push_back( a[ tl ] );
t[ v ].ans = 0;
return;
}
int mid = ( tl + tr ) / 2;
build( v + v, tl, mid );
build( v + v + 1, mid + 1, tr );
t[ v ] = t[ v + v ] + t[ v + v + 1 ];
}
void gett( int v, int tl, int tr, int l, int r ) {
if ( tl > r || tr < l )
return;
if ( tl >= l && tr <= r ) {
an.ans = max( an.ans, t[ v ].ans );
if ( an.mx > t[ v ].v.front() ) {
auto it = lower_bound( t[ v ].v.begin(), t[ v ].v.end(), an.mx );
it = --it;
an.ans = max( an.ans, an.mx + *it );
}
an.mx = max( an.mx, t[ v ].v.back() );
return;
}
int mid = ( tl + tr ) / 2;
gett( v + v, tl, mid, l, r );
gett( v + v + 1, mid + 1, tr, l, r );
}
struct Node2 {
int mn, mx, inv;
public :
Node2 operator + ( Node2 a ) {
Node2 c;
c.inv = max( inv, a.inv );
if ( a.mn < mx )
c.inv = 1;
c.mn = min( mn, a.mn );
c.mx = max( mx, a.mx );
return c;
}
} t1[ 4000001 ];
void build1( int v, int tl, int tr ) {
if ( tl == tr ) {
t1[ v ].mn = a[ tl ];
t1[ v ].mx = a[ tl ];
t1[ v ].inv = 0;
return;
}
int mid = ( tl + tr ) / 2;
build1( v + v, tl, mid );
build1( v + v + 1, mid + 1, tr );
t1[ v ] = t1[ v + v ] + t1[ v + v + 1 ];
}
void gett1( int v, int tl, int tr, int l, int r ) {
if ( tl > r || tr < l )
return;
if ( tl >= l && tr <= r ) {
if ( t1[ v ].mn < mx || t1[ v ].inv )
num = 1;
mx = max( mx, t1[ v ].mx + 0ll );
return;
}
int mid = ( tl + tr ) / 2;
gett1( v + v, tl, mid, l, r );
gett1( v + v + 1, mid + 1, tr, l, r );
}
main () {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for ( int i = 1; i <= n; i ++ ) {
cin >> a[ i ];
}
int l, r, x;
// if ( n <= 2e5 && m <= 2e5 )
// build( 1, 1, n );
// else
build1( 1, 1, n );
while ( m -- ) {
cin >> l >> r >> x;
// if ( n <= 2e5 && m <= 2e5 ) {
num = 0;
an.mx = 0;
an.ans = 0;
gett( 1, 1, n, l, r );
cout << ( x >= an.ans ) << "\n";
// }
// else {
// num = 0;
// mx = -1;
// gett1( 1, 1, n, l, r );
// cout << !num << "\n";
// }
}
}
/*
9 1
10 6 7 10 1 3 7 3 7
2 3 1
3 1
7 1 9
1 3 8
*/
Compilation message
sortbooks.cpp: In member function 'Node Node::operator+(Node)':
sortbooks.cpp:54:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | while ( l < v.size() && r < a.v.size() ) {
| ~~^~~~~~~~~~
sortbooks.cpp:54:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | while ( l < v.size() && r < a.v.size() ) {
| ~~^~~~~~~~~~~~
sortbooks.cpp:66:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | while ( l < v.size() ) {
| ~~^~~~~~~~~~
sortbooks.cpp:70:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | while ( r < a.v.size() ) {
| ~~^~~~~~~~~~~~
sortbooks.cpp: At global scope:
sortbooks.cpp:159:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
159 | main () {
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
147 ms |
254340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
147 ms |
254340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
295 ms |
262144 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
154 ms |
261484 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
147 ms |
254340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
147 ms |
254340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
