Submission #1010927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010927		LucaIlie	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	678 ms	104024 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

struct update {
    int l, r, k;
};

struct query {
    int l, r, k, ans;
};

const int MAX_N = 1e6;
const int MAX_Q = 1e6;
const int INF = 1e9 + 1;
int v[MAX_N + 1];
update updates[MAX_N + 1];
query queries[MAX_Q];
vector<int> queriesByR[MAX_N + 1];

struct AIB_SUF {
    int aib[MAX_N + 2];

    void update( int i, int x ) {
        i = MAX_N + 1 - i;
        while ( i <= MAX_N ) {
            aib[i] = max( aib[i], x );
            i += (i & -i);
        }
    }

    int query( int i ) {
        i = MAX_N + 1 - i;
        int x = 0;
        while ( i > 0 ) {
            x = max( x, aib[i] );
            i -= (i & -i);
        }
        return x;
    }
} maxKSuf;

int main() {
    cin.tie( NULL );
    ios_base::sync_with_stdio( false );
    
    int n, q;

    cin >> n >> q;
    v[0] = INF;
    for ( int i = 1; i <= n; i++ )
        cin >> v[i];
    for ( int i = 0; i < q; i++ )
        cin >> queries[i].l >> queries[i].r >> queries[i].k;

    vector<int> stack;
    stack.push_back( 0 );
    for ( int i = 1; i <= n; i++ ) {
        while ( !stack.empty() && v[i] >= v[stack.back()] )
            stack.pop_back();
        updates[i] = { stack.back(), i, v[stack.back()] + v[i] };
        stack.push_back( i );
    }

    for ( int i = 0; i < q; i++ )
        queriesByR[queries[i].r].push_back( i );

    for ( int i = 1; i <= n; i++ ) {
        maxKSuf.update( updates[i].l, updates[i].k );
        for ( int j: queriesByR[i] )
            queries[j].ans = maxKSuf.query( queries[j].l );
    }

    for ( int i = 0; i < q; i++ )
        cout << (queries[i].ans <= queries[i].k) << "\n";


    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23