oj.uz

Submission #579025

# Submission time Handle Problem Language Result Execution time Memory
579025 2022-06-18T10:05:04 Z LucaIlie Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 1290 ms 262144 KB 
#include <bits/stdc++.h>
 
#define MAX_N 1000000
 
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 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 );
    }
 
signed main() {
    int n, m, l, r, k, i;
 
    cin >> n >> m;
    for ( i = 0; i < n; i++ )
        cin >> w[i];
 
    init( 0, 0, n - 1 );
 
    for ( i = 0; i < m; i++ ) {
        cin >> l >> r >> k;
 
        query( 0, 0, n - 1, l - 1, r - 1 );
 
        if ( ans.maxEfort > k )
            cout << "0\n";
        else
            cout << "1\n";
    }
 
    return 0;
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 125516 KB Output is correct
2 Correct 57 ms 125516 KB Output is correct
3 Correct 69 ms 125544 KB Output is correct
4 Correct 61 ms 125440 KB Output is correct
5 Correct 59 ms 125500 KB Output is correct
6 Correct 65 ms 125536 KB Output is correct
7 Correct 61 ms 125524 KB Output is correct
8 Correct 69 ms 125524 KB Output is correct
9 Correct 60 ms 125548 KB Output is correct
10 Correct 63 ms 125536 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 125516 KB Output is correct
2 Correct 57 ms 125516 KB Output is correct
3 Correct 69 ms 125544 KB Output is correct
4 Correct 61 ms 125440 KB Output is correct
5 Correct 59 ms 125500 KB Output is correct
6 Correct 65 ms 125536 KB Output is correct
7 Correct 61 ms 125524 KB Output is correct
8 Correct 69 ms 125524 KB Output is correct
9 Correct 60 ms 125548 KB Output is correct
10 Correct 63 ms 125536 KB Output is correct
11 Correct 69 ms 125700 KB Output is correct
12 Correct 74 ms 126196 KB Output is correct
13 Correct 85 ms 126200 KB Output is correct
14 Correct 96 ms 126092 KB Output is correct
15 Correct 86 ms 126156 KB Output is correct
16 Correct 78 ms 126212 KB Output is correct
17 Correct 72 ms 125924 KB Output is correct
18 Correct 73 ms 126156 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 918 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 139284 KB Output is correct
2 Correct 504 ms 139468 KB Output is correct
3 Correct 541 ms 139396 KB Output is correct
4 Correct 543 ms 139464 KB Output is correct
5 Correct 500 ms 139512 KB Output is correct
6 Correct 464 ms 139472 KB Output is correct
7 Correct 485 ms 139480 KB Output is correct
8 Correct 433 ms 139492 KB Output is correct
9 Correct 307 ms 125896 KB Output is correct
10 Correct 486 ms 139424 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 125516 KB Output is correct
2 Correct 57 ms 125516 KB Output is correct
3 Correct 69 ms 125544 KB Output is correct
4 Correct 61 ms 125440 KB Output is correct
5 Correct 59 ms 125500 KB Output is correct
6 Correct 65 ms 125536 KB Output is correct
7 Correct 61 ms 125524 KB Output is correct
8 Correct 69 ms 125524 KB Output is correct
9 Correct 60 ms 125548 KB Output is correct
10 Correct 63 ms 125536 KB Output is correct
11 Correct 69 ms 125700 KB Output is correct
12 Correct 74 ms 126196 KB Output is correct
13 Correct 85 ms 126200 KB Output is correct
14 Correct 96 ms 126092 KB Output is correct
15 Correct 86 ms 126156 KB Output is correct
16 Correct 78 ms 126212 KB Output is correct
17 Correct 72 ms 125924 KB Output is correct
18 Correct 73 ms 126156 KB Output is correct
19 Correct 1275 ms 153888 KB Output is correct
20 Correct 1290 ms 154056 KB Output is correct
21 Correct 1097 ms 154064 KB Output is correct
22 Correct 1057 ms 154024 KB Output is correct
23 Correct 1109 ms 153952 KB Output is correct
24 Correct 1027 ms 154064 KB Output is correct
25 Correct 1018 ms 154040 KB Output is correct
26 Correct 1126 ms 153940 KB Output is correct
27 Correct 1139 ms 153988 KB Output is correct
28 Correct 1154 ms 154060 KB Output is correct
29 Correct 1169 ms 154132 KB Output is correct
30 Correct 1195 ms 154088 KB Output is correct
31 Correct 1171 ms 154160 KB Output is correct
32 Correct 1254 ms 154264 KB Output is correct
33 Correct 1174 ms 154004 KB Output is correct
34 Correct 1029 ms 154012 KB Output is correct
35 Correct 1111 ms 154152 KB Output is correct
36 Correct 1000 ms 154192 KB Output is correct
37 Correct 1008 ms 154140 KB Output is correct
38 Correct 994 ms 154168 KB Output is correct
39 Correct 1008 ms 154044 KB Output is correct
40 Correct 810 ms 142332 KB Output is correct
41 Correct 1012 ms 154012 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 125516 KB Output is correct
2 Correct 57 ms 125516 KB Output is correct
3 Correct 69 ms 125544 KB Output is correct
4 Correct 61 ms 125440 KB Output is correct
5 Correct 59 ms 125500 KB Output is correct
6 Correct 65 ms 125536 KB Output is correct
7 Correct 61 ms 125524 KB Output is correct
8 Correct 69 ms 125524 KB Output is correct
9 Correct 60 ms 125548 KB Output is correct
10 Correct 63 ms 125536 KB Output is correct
11 Correct 69 ms 125700 KB Output is correct
12 Correct 74 ms 126196 KB Output is correct
13 Correct 85 ms 126200 KB Output is correct
14 Correct 96 ms 126092 KB Output is correct
15 Correct 86 ms 126156 KB Output is correct
16 Correct 78 ms 126212 KB Output is correct
17 Correct 72 ms 125924 KB Output is correct
18 Correct 73 ms 126156 KB Output is correct
19 Runtime error 918 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -