Submission #992796

#	Time	Username	Problem	Language	Result	Execution time	Memory
992796		NValchanov	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	790 ms	60452 KiB

sortbooks

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;

struct SegmentTree
{
    int n;
    ll tree[4 * MAXN];
    ll w[MAXN];

    void init(int _n, ll _w[])
    {
        n = _n;
        for(int i = 1; i <= n; i++)
        {
            w[i] = _w[i];
        }
    }

    void update(int left, int right, int idx, int pos, ll val)
    {
        if(pos < left || right < pos)
            return;

        if(left == right)
        {
            tree[idx] = max(tree[idx], val + w[left]);
            return;
        }

        int mid = left + (right - left) / 2;

        update(left, mid, 2 * idx, pos, val);
        update(mid + 1, right, 2 * idx + 1, pos, val);

        tree[idx] = max(tree[2 * idx], tree[2 * idx + 1]);
    } 

    ll query(int left, int right, int idx, int qleft, int qright)
    {
        if(qright < left || right < qleft)
            return 0;

        if(qleft <= left && right <= qright)
            return tree[idx];

        int mid = left + (right - left) / 2;

        ll Lnode = query(left, mid, 2 * idx, qleft, qright);
        ll Rnode = query(mid + 1, right, 2 * idx + 1, qleft, qright);

        return max(Lnode, Rnode);
    }

    void update(int pos, ll val)
    {
        update(1, n, 1, pos, val);
    }

    ll query(int left, int right)
    {
        return query(1, n, 1, left, right);
    }
};

struct qry
{
    int left, right;
    ll k;
    int idx;

    qry()
    {
        left = right = 1;
        k = 0;
        idx = 1;
    }

    qry(int _left, int _right, ll _k, int _idx)
    {
        left = _left;
        right = _right;
        k = _k;
        idx = _idx;
    }

    friend bool operator<(const qry&q1, const qry&q2)
    {
        if(q1.right != q2.right)
            return q1.right < q2.right;

        if(q1.left != q2.left)
            return q1.left < q2.left;

        if(q1.k != q2.k)
            return q1.k < q2.k;
        
        return q1.idx < q2.idx;
    }
};

int n, q;
ll w[MAXN];
bool ans[MAXN];
vector < qry > queries;
SegmentTree t;

void read()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i];
    }
    for(int i = 1; i <= q; i++)
    {
        int left, right;
        ll k;
        cin >> left >> right >> k;
        qry cur = qry(left, right, k, i);

        queries.push_back(cur);
    }
}

void solve()
{
    t.init(n, w);
    sort(queries.begin(), queries.end());

    stack < int > st;
    int ptr = 1;

    for(qry c : queries)
    {
        int left = c.left;
        int right = c.right;
        ll k = c.k;
        int idx =  c.idx;

        while(ptr <= right)
        {
            while(!st.empty() && w[st.top()] <= w[ptr])
                st.pop();

            if(!st.empty())
                t.update(st.top(), w[ptr]);

            st.push(ptr);

            ptr++;
        }

        ll cur = t.query(left, right);

        ans[idx] = (cur <= k);
    }
}

void print()
{
    for(int i = 1; i <= q; i++)
    {
        cout << ans[i] << endl;
    }
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    read();
    solve();
    print();

    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