Submission #861920

#	Time	Username	Problem	Language	Result	Execution time	Memory
861920		velislavgarkov	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1040 ms	94964 KiB

sortbooks

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
#define endl '\n'
const int MAXN=1e6+10;
struct Element {
    int l;
    int k;
    int ind;
};
int a[MAXN];
bool ans[MAXN];
vector <Element> que[MAXN];
stack <int> st;
int tree[4*MAXN];
void update(int node, int l, int r, int qind, int ch) {
    if (qind>r || qind<l) return;
    if (l==r) {
        tree[node]=ch;
        return;
    }
    int mid=(l+r)/2;
    update(node*2,l,mid,qind,ch);
    update(node*2+1,mid+1,r,qind,ch);
    tree[node]=max(tree[node*2],tree[node*2+1]);
}
int query(int node, int l, int r, int ql, int qr) {
    if (ql>r || qr<l) return -1;
    if (l>=ql && r<=qr) return tree[node];
    int mid=(l+r)/2;
    return max(query(node*2,l,mid,ql,qr),query(node*2+1,mid+1,r,ql,qr));
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i=1;i<=n;i++) cin >> a[i];
    int l, r, k;
    for (int i=0;i<m;i++) {
        cin >> l >> r >> k;
        que[r].push_back({l,k,i});
    }
    for (int i=1;i<=n;i++) {
        while (!st.empty() && a[i]>=a[st.top()]) st.pop();
        if (!st.empty()) update(1,1,n,st.top(),a[i]+a[st.top()]);
        st.push(i);
        for (auto cur:que[i]) {
            ans[cur.ind]=(query(1,1,n,cur.l,i)<=cur.k);
        }
    }
    for (int i=0;i<m;i++) cout << ans[i] << endl;
    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