Submission #171208

#	Time	Username	Problem	Language	Result	Execution time	Memory
171208		donentseto	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1223 ms	89664 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
int n, m, a [1000006];
struct query{
    int l, k, idx;
};
vector <query> v [1000006];
bool ans [1000006];
int bst [1000006];
void upd (int x, int val){
    while (x <= n){
        bst [x] = max (bst [x], val);
        x += x & -x;
    }
}
int q (int x){
    int ans = 0;
    while (x > 0){
        ans = max (ans, bst [x]);
        x -= x & -x;
    }
    return ans;
}
int main (){

    ios::sync_with_stdio (false);
    cin.tie (0);

    cin >> n >> m;
    
    for (int i = 0; i < n; i ++) cin >> a [i];
    for (int i = 0; i < m; i ++){
        int l, r, k;
        cin >> l >> r >> k;
        v [r - 1].push_back ({l - 1, k, i});
    }

    stack <pair <int, int> > s;
    for (int i = 0; i < n; i ++){
        while (!s.empty () && s.top ().first <= a [i]) s.pop ();
        if (!s.empty ()) upd (n - s.top ().second, s.top ().first + a [i]);
        s.push ({a [i], i});
        for (auto Q : v [i]){
            if (q (n - Q.l) <= Q.k) ans [Q.idx] = 1;
            else ans [Q.idx] = 0;
        }
    }
    for (int i = 0; i < m; i ++) cout << ans [i] << '\n';

}

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