oj.uz

Submission #578993

# Submission time Handle Problem Language Result Execution time Memory
578993 2022-06-18T09:33:38 Z LucaIlie Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 1379 ms 83836 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 14 ms 31572 KB Output is correct
2 Correct 17 ms 31592 KB Output is correct
3 Correct 16 ms 31572 KB Output is correct
4 Correct 16 ms 31572 KB Output is correct
5 Correct 18 ms 31572 KB Output is correct
6 Correct 17 ms 31700 KB Output is correct
7 Correct 16 ms 31600 KB Output is correct
8 Correct 17 ms 31572 KB Output is correct
9 Correct 16 ms 31572 KB Output is correct
10 Correct 15 ms 31572 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31572 KB Output is correct
2 Correct 17 ms 31592 KB Output is correct
3 Correct 16 ms 31572 KB Output is correct
4 Correct 16 ms 31572 KB Output is correct
5 Correct 18 ms 31572 KB Output is correct
6 Correct 17 ms 31700 KB Output is correct
7 Correct 16 ms 31600 KB Output is correct
8 Correct 17 ms 31572 KB Output is correct
9 Correct 16 ms 31572 KB Output is correct
10 Correct 15 ms 31572 KB Output is correct
11 Correct 30 ms 31912 KB Output is correct
12 Correct 27 ms 32628 KB Output is correct
13 Correct 27 ms 32700 KB Output is correct
14 Correct 40 ms 32696 KB Output is correct
15 Correct 44 ms 32716 KB Output is correct
16 Correct 36 ms 32772 KB Output is correct
17 Correct 28 ms 32292 KB Output is correct
18 Correct 31 ms 32648 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 55420 KB Output is correct
2 Correct 523 ms 55476 KB Output is correct
3 Correct 542 ms 55516 KB Output is correct
4 Correct 493 ms 55404 KB Output is correct
5 Correct 512 ms 55516 KB Output is correct
6 Correct 460 ms 55356 KB Output is correct
7 Correct 433 ms 55372 KB Output is correct
8 Correct 447 ms 55188 KB Output is correct
9 Correct 229 ms 33180 KB Output is correct
10 Correct 445 ms 55172 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31572 KB Output is correct
2 Correct 17 ms 31592 KB Output is correct
3 Correct 16 ms 31572 KB Output is correct
4 Correct 16 ms 31572 KB Output is correct
5 Correct 18 ms 31572 KB Output is correct
6 Correct 17 ms 31700 KB Output is correct
7 Correct 16 ms 31600 KB Output is correct
8 Correct 17 ms 31572 KB Output is correct
9 Correct 16 ms 31572 KB Output is correct
10 Correct 15 ms 31572 KB Output is correct
11 Correct 30 ms 31912 KB Output is correct
12 Correct 27 ms 32628 KB Output is correct
13 Correct 27 ms 32700 KB Output is correct
14 Correct 40 ms 32696 KB Output is correct
15 Correct 44 ms 32716 KB Output is correct
16 Correct 36 ms 32772 KB Output is correct
17 Correct 28 ms 32292 KB Output is correct
18 Correct 31 ms 32648 KB Output is correct
19 Correct 1243 ms 83552 KB Output is correct
20 Correct 1286 ms 83680 KB Output is correct
21 Correct 1172 ms 83576 KB Output is correct
22 Correct 1082 ms 83496 KB Output is correct
23 Correct 1155 ms 83472 KB Output is correct
24 Correct 996 ms 83284 KB Output is correct
25 Correct 1047 ms 83528 KB Output is correct
26 Correct 1171 ms 83556 KB Output is correct
27 Correct 1247 ms 83520 KB Output is correct
28 Correct 1247 ms 83624 KB Output is correct
29 Correct 1310 ms 83836 KB Output is correct
30 Correct 1167 ms 83648 KB Output is correct
31 Correct 1364 ms 83636 KB Output is correct
32 Correct 1293 ms 83636 KB Output is correct
33 Correct 1379 ms 83740 KB Output is correct
34 Correct 973 ms 83348 KB Output is correct
35 Correct 985 ms 83228 KB Output is correct
36 Correct 977 ms 83056 KB Output is correct
37 Correct 1006 ms 83104 KB Output is correct
38 Correct 986 ms 83176 KB Output is correct
39 Correct 1028 ms 82264 KB Output is correct
40 Correct 807 ms 61660 KB Output is correct
41 Correct 1008 ms 81852 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31572 KB Output is correct
2 Correct 17 ms 31592 KB Output is correct
3 Correct 16 ms 31572 KB Output is correct
4 Correct 16 ms 31572 KB Output is correct
5 Correct 18 ms 31572 KB Output is correct
6 Correct 17 ms 31700 KB Output is correct
7 Correct 16 ms 31600 KB Output is correct
8 Correct 17 ms 31572 KB Output is correct
9 Correct 16 ms 31572 KB Output is correct
10 Correct 15 ms 31572 KB Output is correct
11 Correct 30 ms 31912 KB Output is correct
12 Correct 27 ms 32628 KB Output is correct
13 Correct 27 ms 32700 KB Output is correct
14 Correct 40 ms 32696 KB Output is correct
15 Correct 44 ms 32716 KB Output is correct
16 Correct 36 ms 32772 KB Output is correct
17 Correct 28 ms 32292 KB Output is correct
18 Correct 31 ms 32648 KB Output is correct
19 Runtime error 129 ms 69132 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -