oj.uz

Submission #521810

# Submission time Handle Problem Language Result Execution time Memory
521810 2022-02-03T08:21:27 Z LucaIlie Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
8 / 100
 277 ms 262148 KB 
#include <bits/stdc++.h>

#define MAX_N 200000
#define MAX_LOG_N 19
#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 sparseTable {
    struct nod {
        int maxW, maxEfort;
        vector <int> v;
    };

    int n;
    nod table[MAX_N][MAX_LOG_N + 1];

    void init( int x[], int m ) {
        int i, p, i1, i2;

        n = m;

        for ( i = 0; i < n; i++ ) {
            table[i][0].maxW = x[i];
            table[i][0].maxEfort = 0;
            table[i][0].v.push_back( x[i] );
        }
        for ( p = 1; (1 << p) <= n; p++ ) {
            for ( i = 0; i <= n - (1 << p); i++ ) {
                table[i][p].maxW = max( table[i][p - 1].maxW, table[i + (1 << (p - 1))][p - 1].maxW );
                table[i][p].maxEfort = max( max( table[i][p - 1].maxEfort, table[i + (1 << (p - 1))][p - 1].maxEfort ), table[i][p - 1].maxW + lower( table[i + (1 << (p - 1))][p - 1].v, table[i][p - 1].maxW ) );

                i1 = i2 = 0;
                while ( i1 < table[i][p - 1].v.size() && i2 < table[i + (1 << (p - 1))][p - 1].v.size() ) {
                    if ( table[i][p - 1].v[i1] < table[i + (1 << (p - 1))][p - 1].v[i2] ) {
                        table[i][p].v.push_back( table[i][p - 1].v[i1] );
                        i1++;
                    } else {
                        table[i][p].v.push_back( table[i + (1 << (p - 1))][p - 1].v[i2] );
                        i2++;
                    }
                }
                while ( i1 < table[i][p - 1].v.size() ) {
                    table[i][p].v.push_back( table[i][p - 1].v[i1] );
                    i1++;
                }
                while ( i2 < table[i + (1 << (p - 1))][p - 1].v.size() ) {
                    table[i][p].v.push_back( table[i + (1 << (p - 1))][p - 1].v[i2] );
                    i2++;
                }
            }
        }
    }

    int query( int l, int r ) {
        int len, e, mW, p;

        len = r - l + 1;

        e = 0;
        mW = 0;
        for ( p = 0; (1 << p) <= len; p++ ) {
            if ( len & (1 << p) ) {
                e = max( max( e, table[l][p].maxEfort ), mW + lower( table[l][p].v, mW ) );
                mW = max( mW, table[l][p].maxW );
                l += (1 << p);
            }
        }

        return e;
    }
};

sparseTable shelf;

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

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

    shelf.init( w, n );

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

        if ( shelf.query( l - 1, r - 1 ) > k )
            cout << "0\n";
        else
            cout << "1\n";
    }

    return 0;
}

Compilation message

sortbooks.cpp: In member function 'void sparseTable::init(long long int*, long long int)':
sortbooks.cpp:53:28: 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]
   53 |                 while ( i1 < table[i][p - 1].v.size() && i2 < table[i + (1 << (p - 1))][p - 1].v.size() ) {
      |                         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:53:61: 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]
   53 |                 while ( i1 < table[i][p - 1].v.size() && i2 < table[i + (1 << (p - 1))][p - 1].v.size() ) {
      |                                                          ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:62:28: 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]
   62 |                 while ( i1 < table[i][p - 1].v.size() ) {
      |                         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:66:28: 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]
   66 |                 while ( i2 < table[i + (1 << (p - 1))][p - 1].v.size() ) {
      |                         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 156776 KB Output is correct
2 Correct 75 ms 156804 KB Output is correct
3 Correct 70 ms 156852 KB Output is correct
4 Correct 69 ms 156748 KB Output is correct
5 Correct 69 ms 156980 KB Output is correct
6 Correct 70 ms 158176 KB Output is correct
7 Correct 70 ms 158148 KB Output is correct
8 Correct 74 ms 158108 KB Output is correct
9 Correct 67 ms 157180 KB Output is correct
10 Correct 69 ms 158148 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 156776 KB Output is correct
2 Correct 75 ms 156804 KB Output is correct
3 Correct 70 ms 156852 KB Output is correct
4 Correct 69 ms 156748 KB Output is correct
5 Correct 69 ms 156980 KB Output is correct
6 Correct 70 ms 158176 KB Output is correct
7 Correct 70 ms 158148 KB Output is correct
8 Correct 74 ms 158108 KB Output is correct
9 Correct 67 ms 157180 KB Output is correct
10 Correct 69 ms 158148 KB Output is correct
11 Correct 94 ms 169140 KB Output is correct
12 Runtime error 177 ms 262148 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 156776 KB Output is correct
2 Correct 75 ms 156804 KB Output is correct
3 Correct 70 ms 156852 KB Output is correct
4 Correct 69 ms 156748 KB Output is correct
5 Correct 69 ms 156980 KB Output is correct
6 Correct 70 ms 158176 KB Output is correct
7 Correct 70 ms 158148 KB Output is correct
8 Correct 74 ms 158108 KB Output is correct
9 Correct 67 ms 157180 KB Output is correct
10 Correct 69 ms 158148 KB Output is correct
11 Correct 94 ms 169140 KB Output is correct
12 Runtime error 177 ms 262148 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 156776 KB Output is correct
2 Correct 75 ms 156804 KB Output is correct
3 Correct 70 ms 156852 KB Output is correct
4 Correct 69 ms 156748 KB Output is correct
5 Correct 69 ms 156980 KB Output is correct
6 Correct 70 ms 158176 KB Output is correct
7 Correct 70 ms 158148 KB Output is correct
8 Correct 74 ms 158108 KB Output is correct
9 Correct 67 ms 157180 KB Output is correct
10 Correct 69 ms 158148 KB Output is correct
11 Correct 94 ms 169140 KB Output is correct
12 Runtime error 177 ms 262148 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -