oj.uz

Submission #521811

# Submission time Handle Problem Language Result Execution time Memory
521811 2022-02-03T08:22:09 Z LucaIlie Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
8 / 100
 309 ms 262148 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 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 60 ms 141116 KB Output is correct
2 Correct 60 ms 141072 KB Output is correct
3 Correct 65 ms 141356 KB Output is correct
4 Correct 61 ms 141168 KB Output is correct
5 Correct 61 ms 141376 KB Output is correct
6 Correct 68 ms 142532 KB Output is correct
7 Correct 65 ms 142488 KB Output is correct
8 Correct 63 ms 142540 KB Output is correct
9 Correct 65 ms 141508 KB Output is correct
10 Correct 65 ms 142484 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 141116 KB Output is correct
2 Correct 60 ms 141072 KB Output is correct
3 Correct 65 ms 141356 KB Output is correct
4 Correct 61 ms 141168 KB Output is correct
5 Correct 61 ms 141376 KB Output is correct
6 Correct 68 ms 142532 KB Output is correct
7 Correct 65 ms 142488 KB Output is correct
8 Correct 63 ms 142540 KB Output is correct
9 Correct 65 ms 141508 KB Output is correct
10 Correct 65 ms 142484 KB Output is correct
11 Correct 87 ms 153528 KB Output is correct
12 Runtime error 188 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 246 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 309 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 60 ms 141116 KB Output is correct
2 Correct 60 ms 141072 KB Output is correct
3 Correct 65 ms 141356 KB Output is correct
4 Correct 61 ms 141168 KB Output is correct
5 Correct 61 ms 141376 KB Output is correct
6 Correct 68 ms 142532 KB Output is correct
7 Correct 65 ms 142488 KB Output is correct
8 Correct 63 ms 142540 KB Output is correct
9 Correct 65 ms 141508 KB Output is correct
10 Correct 65 ms 142484 KB Output is correct
11 Correct 87 ms 153528 KB Output is correct
12 Runtime error 188 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 60 ms 141116 KB Output is correct
2 Correct 60 ms 141072 KB Output is correct
3 Correct 65 ms 141356 KB Output is correct
4 Correct 61 ms 141168 KB Output is correct
5 Correct 61 ms 141376 KB Output is correct
6 Correct 68 ms 142532 KB Output is correct
7 Correct 65 ms 142488 KB Output is correct
8 Correct 63 ms 142540 KB Output is correct
9 Correct 65 ms 141508 KB Output is correct
10 Correct 65 ms 142484 KB Output is correct
11 Correct 87 ms 153528 KB Output is correct
12 Runtime error 188 ms 262148 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -