Submission #169353

#	Time	Username	Problem	Language	Result	Execution time	Memory
169353		Nodir_Bobiev	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	17 / 100	3034 ms	91760 KiB

sortbooks

# include <bits/stdc++.h>
# define FILE
using namespace std;

const int N = 1e6 + 100; 

int n, m, w[N], l[N], ls[N], rs[N], ks[N], ans[N], mx[4*N];
vector < int > ids[N];

void update( int pos, int val, int tl = 1, int tr = n, int td = 1 ){
    if( tl == tr )
        mx[td] = max( mx[td], val );
    else{
        int tm = ( tl+tr ) >> 1;
        if( pos <= tm )
            update( pos, val, tl, tm, td+td );
        else
            update( pos, val, tm+1, tr, td+td+1 );
        mx[td] = max( mx[td+td], mx[td+td+1] );
    }
}
int get( int l, int r, int tl = 1, int tr = n, int td = 1 ){
    if( l > r || l > tr || tl > r || tl > tr )
        return 0;
    if( l <= tl && tr <= r )
        return mx[td];
    else{
        int tm = ( tl + tr )>> 1;
        return max( get( l, r, tl, tm, td+td ), get( l,r, tm+1, tr, td+td+1 )) ;
    }
}

int main(){

    # ifdef FILEs
        freopen( "input.txt", "r", stdin );
        freopen( "output.txt", "w", stdout );
    # endif
    ios_base::sync_with_stdio( false );
    
    cin >> n >> m;
    for( int i = 1; i <= n; i ++ ){
        cin >> w[i];
        l[i] = i-1;
        while(l[i] && w[l[i]] <= w[i] ){
            l[i] = l[l[i]];
        }
    }
    for( int i = 1; i <= m; i ++ ){
        cin >> ls[i] >> rs[i] >> ks[i];
        ids[rs[i]].push_back( i );
    }
    for( int i = 1; i <= n; i ++ ){
        update( l[i], w[i] + w[l[i]] );
        for( auto id: ids[i] ){
            ans[id] = (get( ls[id], i ) <= ks[id]);
        }
    }
    for( int i = 1; i <= m; i++ ){
        cout << ans[i] << endl;
    }





}

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