Submission #877889

#	Time	Username	Problem	Language	Result	Execution time	Memory
877889		TahirAliyev	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1780 ms	98824 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;


#define ll long long int
#define pii pair<int, int>
#define oo 1e9

const int MAX = 1e6 + 6;

int n, m;
int tree[4 * MAX];
int arr[MAX];

void update(int node, int l, int r, int pos, int val){
    if(l == r){
        tree[node] = max(tree[node], val);
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid) update(2 * node, l, mid, pos, val);
    else update(2 * node + 1, mid + 1, r, pos, val);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

int ask(int node, int l, int r, int ql, int qr){
    if(r < ql || qr < l) return 0;
    if(ql <= l && r <= qr) return tree[node];
    int mid = (l + r) / 2;
    return max(ask(2 * node, l, mid , ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
}

vector<pii> q[MAX];
int ans[MAX];
int k[MAX];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    for(int i = 1; i <= m; i++){
        int l, r, a; cin >> l >> r >> a;
        k[i] = a;
        q[r].push_back({l, i});
    }
    stack<pii> s;
    for(int r = 1; r <= n; r++){
        while(s.size() && s.top().first <= arr[r]){
            s.pop();
        }
        if(s.size()) update(1, 1, n, s.top().second, arr[r] + s.top().first);
        s.push({arr[r], r});
        for(pii l : q[r]){
            ans[l.second] = ask(1, 1, n, l.first, r);
        }
    }
    for(int i = 1; i <= m; i++){
        if(ans[i] <= k[i]) cout << "1\n";
        else cout << "0\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