oj.uz

Submission #521824

# Submission time Handle Problem Language Result Execution time Memory
521824 2022-02-03T09:02:58 Z LucaIlie Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 77672 KB 
#include <bits/stdc++.h>

#define MAX_N 200000
#define MAX_LOG_N 17
#define int long long

using namespace std;

int w[MAX_N];

int lower( vector <int> v, int x ) {
    int l, r, mid;

    l = 0;
    r = v.size();
    while ( r - l > 1 ) {
        mid = (l + r) / 2;

        if ( v[mid] < x )
            l = mid;
        else
            r = mid;
    }

    return v[l] < x ? v[l] : -x;
}


struct AINT {
    struct nod {
        int maxEffort, maxW;
        vector <int> v;
    };

    struct answer {
        int maxEfort, maxW;
    };

    nod aint[4 * MAX_N];
    answer ans;

    void init( int nod, int l, int r ) {
        int mid, i, j;

        if ( l == r ) {
            aint[nod].maxEffort = 0;
            aint[nod].maxW = w[l];
            aint[nod].v.push_back( w[l] );
            return;
        }

        mid = (l + r) / 2;
        init( nod * 2 + 1, l, mid );
        init( nod * 2 + 2, mid + 1, r );

        aint[nod].maxW = max( aint[nod * 2 + 1].maxW, aint[nod * 2 + 2].maxW );
        aint[nod].maxEffort = max( max( aint[nod * 2 + 1].maxEffort, aint[nod * 2 + 2].maxEffort ), aint[nod * 2 + 1].maxW + lower( aint[nod * 2 + 2].v, aint[nod * 2 + 1].maxW ) );

        i = j = 0;
        while ( i < aint[nod * 2 + 1].v.size() && j < aint[nod * 2 + 2].v.size() ) {
            if ( aint[nod * 2 + 1].v[i] < aint[nod * 2 + 2].v[j] ) {
                aint[nod].v.push_back( aint[nod * 2 + 1].v[i] );
                i++;
            } else {
                aint[nod].v.push_back( aint[nod * 2 + 2].v[j] );
                j++;
            }
        }
        while ( i < aint[nod * 2 + 1].v.size() ) {
            aint[nod].v.push_back( aint[nod * 2 + 1].v[i] );
            i++;
        }
        while ( j < aint[nod * 2 + 2].v.size() ) {
            aint[nod].v.push_back( aint[nod * 2 + 2].v[j] );
            j++;
        }
    }

    void query( int nod, int l, int r, int lq, int rq ) {
        int mid;

        if ( nod == 0 )
            ans = { 0, 0 };

        if ( l > rq || r < lq )
            return;

        if ( lq <= l && r <= rq ) {
            ans.maxEfort = max( max( ans.maxEfort, aint[nod].maxEffort ), ans.maxW + lower( aint[nod].v, ans.maxW ) );
            ans.maxW = max( ans.maxW, aint[nod].maxW );
            return;
        }

        mid = (l + r) / 2;
        query( nod * 2 + 1, l, mid, lq, rq );
        query( nod * 2 + 2, mid + 1, r, lq, rq );
    }
};

AINT shelf;

signed main() {
    int n, m, l, r, k, i;

    cin >> n >> m;
    for ( i = 0; i < n; i++ )
        cin >> w[i];

    shelf.init( 0, 0, n - 1 );

    for ( i = 0; i < m; i++ ) {
        cin >> l >> r >> k;

        shelf.query( 0, 0, n - 1, l - 1, r - 1 );

        if ( shelf.ans.maxEfort > k )
            cout << "0\n";
        else
            cout << "1\n";
    }

    return 0;
}

Compilation message

sortbooks.cpp: In member function 'void AINT::init(long long int, long long int, long long int)':
sortbooks.cpp:60:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         while ( i < aint[nod * 2 + 1].v.size() && j < aint[nod * 2 + 2].v.size() ) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:60:53: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         while ( i < aint[nod * 2 + 1].v.size() && j < aint[nod * 2 + 2].v.size() ) {
      |                                                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:69:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         while ( i < aint[nod * 2 + 1].v.size() ) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:73:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         while ( j < aint[nod * 2 + 2].v.size() ) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31564 KB Output is correct
2 Correct 17 ms 31500 KB Output is correct
3 Correct 17 ms 31556 KB Output is correct
4 Correct 16 ms 31608 KB Output is correct
5 Correct 16 ms 31564 KB Output is correct
6 Correct 17 ms 31564 KB Output is correct
7 Correct 17 ms 31564 KB Output is correct
8 Correct 17 ms 31564 KB Output is correct
9 Correct 16 ms 31564 KB Output is correct
10 Correct 17 ms 31564 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31564 KB Output is correct
2 Correct 17 ms 31500 KB Output is correct
3 Correct 17 ms 31556 KB Output is correct
4 Correct 16 ms 31608 KB Output is correct
5 Correct 16 ms 31564 KB Output is correct
6 Correct 17 ms 31564 KB Output is correct
7 Correct 17 ms 31564 KB Output is correct
8 Correct 17 ms 31564 KB Output is correct
9 Correct 16 ms 31564 KB Output is correct
10 Correct 17 ms 31564 KB Output is correct
11 Correct 31 ms 31820 KB Output is correct
12 Correct 27 ms 32628 KB Output is correct
13 Correct 29 ms 32520 KB Output is correct
14 Correct 35 ms 32616 KB Output is correct
15 Correct 35 ms 32588 KB Output is correct
16 Correct 40 ms 32668 KB Output is correct
17 Correct 32 ms 32204 KB Output is correct
18 Correct 36 ms 32712 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 107 ms 66932 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1382 ms 55648 KB Output is correct
2 Execution timed out 3015 ms 54800 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31564 KB Output is correct
2 Correct 17 ms 31500 KB Output is correct
3 Correct 17 ms 31556 KB Output is correct
4 Correct 16 ms 31608 KB Output is correct
5 Correct 16 ms 31564 KB Output is correct
6 Correct 17 ms 31564 KB Output is correct
7 Correct 17 ms 31564 KB Output is correct
8 Correct 17 ms 31564 KB Output is correct
9 Correct 16 ms 31564 KB Output is correct
10 Correct 17 ms 31564 KB Output is correct
11 Correct 31 ms 31820 KB Output is correct
12 Correct 27 ms 32628 KB Output is correct
13 Correct 29 ms 32520 KB Output is correct
14 Correct 35 ms 32616 KB Output is correct
15 Correct 35 ms 32588 KB Output is correct
16 Correct 40 ms 32668 KB Output is correct
17 Correct 32 ms 32204 KB Output is correct
18 Correct 36 ms 32712 KB Output is correct
19 Execution timed out 3105 ms 77672 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31564 KB Output is correct
2 Correct 17 ms 31500 KB Output is correct
3 Correct 17 ms 31556 KB Output is correct
4 Correct 16 ms 31608 KB Output is correct
5 Correct 16 ms 31564 KB Output is correct
6 Correct 17 ms 31564 KB Output is correct
7 Correct 17 ms 31564 KB Output is correct
8 Correct 17 ms 31564 KB Output is correct
9 Correct 16 ms 31564 KB Output is correct
10 Correct 17 ms 31564 KB Output is correct
11 Correct 31 ms 31820 KB Output is correct
12 Correct 27 ms 32628 KB Output is correct
13 Correct 29 ms 32520 KB Output is correct
14 Correct 35 ms 32616 KB Output is correct
15 Correct 35 ms 32588 KB Output is correct
16 Correct 40 ms 32668 KB Output is correct
17 Correct 32 ms 32204 KB Output is correct
18 Correct 36 ms 32712 KB Output is correct
19 Runtime error 107 ms 66932 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -