oj.uz

Submission #521797

# Submission time Handle Problem Language Result Execution time Memory
521797 2022-02-03T07:27:23 Z LucaIlie Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 388 ms 262148 KB 
#include <bits/stdc++.h>

#define MAX_N 100000
#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 )
            r = mid;
        else
            l = 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 v[], int m ) {
        int i, p, i1, i2;

        n = m;

        for ( i = 0; i < n; i++ ) {
            table[i][0].maxW = v[i];
            table[i][0].maxEfort = 0;
            table[i][0].v.push_back( v[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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 78540 KB Output is correct
2 Correct 33 ms 78520 KB Output is correct
3 Correct 34 ms 78668 KB Output is correct
4 Correct 34 ms 78588 KB Output is correct
5 Correct 38 ms 78796 KB Output is correct
6 Correct 38 ms 79972 KB Output is correct
7 Correct 38 ms 79944 KB Output is correct
8 Correct 38 ms 79956 KB Output is correct
9 Correct 37 ms 78960 KB Output is correct
10 Incorrect 42 ms 79856 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 78540 KB Output is correct
2 Correct 33 ms 78520 KB Output is correct
3 Correct 34 ms 78668 KB Output is correct
4 Correct 34 ms 78588 KB Output is correct
5 Correct 38 ms 78796 KB Output is correct
6 Correct 38 ms 79972 KB Output is correct
7 Correct 38 ms 79944 KB Output is correct
8 Correct 38 ms 79956 KB Output is correct
9 Correct 37 ms 78960 KB Output is correct
10 Incorrect 42 ms 79856 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 126 ms 160600 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 388 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 34 ms 78540 KB Output is correct
2 Correct 33 ms 78520 KB Output is correct
3 Correct 34 ms 78668 KB Output is correct
4 Correct 34 ms 78588 KB Output is correct
5 Correct 38 ms 78796 KB Output is correct
6 Correct 38 ms 79972 KB Output is correct
7 Correct 38 ms 79944 KB Output is correct
8 Correct 38 ms 79956 KB Output is correct
9 Correct 37 ms 78960 KB Output is correct
10 Incorrect 42 ms 79856 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 78540 KB Output is correct
2 Correct 33 ms 78520 KB Output is correct
3 Correct 34 ms 78668 KB Output is correct
4 Correct 34 ms 78588 KB Output is correct
5 Correct 38 ms 78796 KB Output is correct
6 Correct 38 ms 79972 KB Output is correct
7 Correct 38 ms 79944 KB Output is correct
8 Correct 38 ms 79956 KB Output is correct
9 Correct 37 ms 78960 KB Output is correct
10 Incorrect 42 ms 79856 KB Output isn't correct
11 Halted 0 ms 0 KB -