Submission #867822

#	Time	Username	Problem	Language	Result	Execution time	Memory
867822		12345678	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1487 ms	119016 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

const int nx=1e6+5;
int n, m, v[nx], l, r, k, ans[nx];
vector<tuple<int, int, int>> d[nx];
stack<int> st;

struct segtree
{
    int d[4*nx], lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        d[i]+=lz[i];
        if (l==r) return void(lz[i]=0);
        lz[2*i]+=lz[i];
        lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void setval(int l, int r, int i, int idx)
    {
        pushlz(l, r, i);
        if (idx<l||r<idx) return;
        if (l==r) return void(d[i]=v[idx]);
        int md=(l+r)/2;
        setval(l, md, 2*i, idx);
        setval(md+1, r, 2*i+1, idx);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int ul, int ur, int vl)
    {
        if (ur<ul) return;
        pushlz(l, r, i);
        if (r<ul||ur<l) return;
        if (ul<=l&&r<=ur) return lz[i]=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ul, ur, vl);
        update(md+1, r, 2*i+1, ul, ur, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        pushlz(l, r, i);
        if (r<ql||qr<l) return INT_MIN;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>v[i];
    for (int i=1; i<=4*n; i++) s.d[i]=INT_MIN;
    v[n+1]=INT_MAX;
    for (int i=0; i<m; i++) cin>>l>>r>>k, d[l].push_back({r, k, i});
    st.push(n+1);
    for (int i=n; i>=1; i--)
    {
        while (st.size()>1&&v[i]>v[st.top()])
        {
            int x=st.top();
            st.pop();
            s.setval(1, n, 1, x);
            s.update(1, n, 1, x+1, st.top()-1, -v[x]);
        }
        s.update(1, n, 1, i+1, st.top()-1, v[i]);
        st.push(i);
        //cout<<i<<": ";
        //for (int j=1; j<=n; j++) cout<<s.query(1, n, 1, j, j)<<' ';
        //cout<<'\n';
        for (auto [a, b, c]:d[i]) ans[c]=s.query(1, n, 1, i+1, a)<=b;
    }
    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