Submission #521789

#	Time	Username	Problem	Language	Result	Execution time	Memory
521789		LucaIlie	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	22 ms	9476 KiB

sortbooks

#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
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23