oj.uz

Submission #521789

# Submission time Handle Problem Language Result Execution time Memory
521789 2022-02-03T06:46:04 Z LucaIlie Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 22 ms 9476 KB 
#include <bits/stdc++.h>

#define MAX_N 1000
#define MAX_LOG_N 19
#define int long long

using namespace std;

int w[MAX_N];

struct sparseTable {
    struct nod {
        int maxW, maxEfort;
        set <int> s;
    };

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

    void init( int v[], int m ) {
        int i, p;

        n = m;

        for ( i = 0; i < n; i++ ) {
            table[i][0].maxW = v[i];
            table[i][0].maxEfort = 0;
            table[i][0].s.insert( -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( table[i][p - 1].maxEfort, table[i + (1 << (p - 1))][p - 1].maxEfort );
                auto x = table[i + (1 << (p - 1))][p - 1].s.lower_bound( -table[i][p - 1].maxW );
                if ( x != table[i + (1 << (p - 1))][p - 1].s.end() && -(*x) <= table[i][p - 1].maxW )
                    table[i][p].maxEfort = max( table[i][p].maxEfort, table[i][p - 1].maxW - (*x) );

                for ( auto it = table[i][p - 1].s.begin(); it != table[i][p - 1].s.end(); it++ )
                    table[i][p].s.insert( *it );
                for ( auto it = table[i + (1 << (p - 1))][p - 1].s.begin(); it != table[i + (1 << (p - 1))][p - 1].s.end(); it++ )
                    table[i][p].s.insert( *it );
            }
        }
    }

    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( e, table[l][p].maxEfort );
                auto x = table[l][p].s.lower_bound( -mW );
                if ( x != table[l][p].s.end() && -(*x) <= mW )
                    e = max( e, mW - (*x) );
                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;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1528 KB Output is correct
3 Correct 3 ms 2064 KB Output is correct
4 Correct 2 ms 1548 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 22 ms 9348 KB Output is correct
7 Correct 22 ms 9368 KB Output is correct
8 Correct 22 ms 9476 KB Output is correct
9 Correct 6 ms 3532 KB Output is correct
10 Incorrect 2 ms 1740 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1528 KB Output is correct
3 Correct 3 ms 2064 KB Output is correct
4 Correct 2 ms 1548 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 22 ms 9348 KB Output is correct
7 Correct 22 ms 9368 KB Output is correct
8 Correct 22 ms 9476 KB Output is correct
9 Correct 6 ms 3532 KB Output is correct
10 Incorrect 2 ms 1740 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 3 ms 2952 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 2 ms 2964 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1528 KB Output is correct
3 Correct 3 ms 2064 KB Output is correct
4 Correct 2 ms 1548 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 22 ms 9348 KB Output is correct
7 Correct 22 ms 9368 KB Output is correct
8 Correct 22 ms 9476 KB Output is correct
9 Correct 6 ms 3532 KB Output is correct
10 Incorrect 2 ms 1740 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1528 KB Output is correct
3 Correct 3 ms 2064 KB Output is correct
4 Correct 2 ms 1548 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 22 ms 9348 KB Output is correct
7 Correct 22 ms 9368 KB Output is correct
8 Correct 22 ms 9476 KB Output is correct
9 Correct 6 ms 3532 KB Output is correct
10 Incorrect 2 ms 1740 KB Output isn't correct
11 Halted 0 ms 0 KB -