Submission #154494

#	Time	Username	Problem	Language	Result	Execution time	Memory
154494		muhammad_hokimiyon	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3098 ms	20880 KiB

sortbooks

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")

#define fi first
#define se second
#define LL long long

using namespace std;

const int N = 1e6 + 7;
const LL mod = 1e9 + 7;
const int B = sqrt(1e5);

int n,q;
int a[N];
pair < int , int > t[4 * N];

void build( int x , int l , int r )
{
    if( l == r ){
        t[x] = {a[l] , l};
        return;
    }
    int m = (l + r) / 2;
    build(x * 2 , l , m);
    build(x * 2 + 1 , m + 1 , r);
    if( t[x * 2].fi >= t[x * 2 + 1].fi )t[x] = t[x * 2];
    else t[x] = t[x * 2 + 1];
}

pair < int , int > get( int x  , int l , int r , int tl , int tr )
{
    if( tl > tr )return {0 , 0};
    if( l == tl && r == tr )return t[x];
    int m = (l + r) / 2;
    if( get( x * 2 , l , m , tl , min(tr , m) ).fi > get( x * 2 + 1 , m + 1, r , max(tl , m + 1) , tr ).fi )
        return get( x * 2 , l , m , tl , min(tr , m) );
    return get( x * 2 + 1 , m + 1, r , max(tl , m + 1) , tr );
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    cin >> n >> q;
    for( int i = 1; i <= n; i++ ){
        cin >> a[i];
    }
    build(1 , 1 , n);
    for( int i = 1; i <= q; i++ ){
        int l,r,x;
        cin >> l >> r >> x;
        pair < int , int > xx = get( 1 , 1 , n , l , r );
        int yy = 0;
        if( xx.se + 1 <= r )yy = get( 1 , 1 , n , xx.se + 1 , r ).fi;
        int ans = 0;
        if( xx.se < r )ans = xx.fi + yy;
        pair < int , int > xxx;
        if( xx.se - 1 >= l )xxx = get( 1 , 1 , n , l , xx.se - 1 );
        if( yy == 0 ){
            yy = get( 1 , 1 , n , xxx.se + 1 , xx.se - 1 ).fi;
        }
        if( xxx.fi > yy ){
            ans = max( ans , xxx.fi + yy );
        }
        if( ans > x )cout << 0 << "\n";
        else cout << 1 << "\n";;
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23