Submission #169361

#	Time	Username	Problem	Language	Result	Execution time	Memory
169361		Nodir_Bobiev	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2199 ms	94172 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
    
    scanf( "%d %d", &n, &m);
    for( int i = 1; i <= n; i ++ ){
        scanf( "%d", 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 ++ ){
        scanf( "%d %d %d", ls+i, rs+i, ks+i );
        ids[rs[i]].push_back( i );
    }
    for( int i = 1; i <= n; i ++ ){
        if( l[i] )
            update( l[i], w[i] + w[l[i]] );
        for( auto id: ids[i] ){
            ans[id] = (get( ls[id], rs[id] ) <= ks[id]);
        }
    }
    for( int i = 1; i <= m; i++ ){
        printf("%d\n", ans[i]);
    }
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf( "%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~~
sortbooks.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf( "%d", w+i );
         ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf( "%d %d %d", ls+i, rs+i, ks+i );
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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