oj.uz

Submission #154494

# Submission time Handle Problem Language Result Execution time Memory
154494 2019-09-22T07:53:23 Z muhammad_hokimiyon Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 3000 ms 20880 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 4 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 4 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3084 ms 20880 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3098 ms 3104 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 4 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 4 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -