Submission #498612

#	Time	Username	Problem	Language	Result	Execution time	Memory
498612		RedBoy	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++11	100 / 100	1292 ms	63916 KiB

sortbooks

#include <iostream>
#include <stack>
#include <vector>
#include <bitset>

using namespace std;

const int N = 1e6 + 5;
const int INF = 2e9;

struct query{
    int ind, l, k;
};

int n, m;
int l[N], v[N], st[4 * N];
stack<int> s;
vector<query> q[N];
bitset<N> bit;

void update(int node, int l, int r, int pos, int val)
{
    if(l == r)
    {
        //cout << "UPDATE: " << node << ' ' << val << '\n';
        st[node] = max(st[node], val);
        return;
    }

    int lNode = node * 2, rNode = node * 2 + 1;
    int mid = (l + r) / 2;

    if(pos <= mid)
        update(lNode, l, mid, pos, val);
    else
        update(rNode, mid + 1, r, pos, val);

    st[node] = max(st[lNode], st[rNode]);
}

int get(int node, int l, int r, int ql, int qr)
{
    if(ql <= l && r <= qr)
        return st[node];

    int lNode = node * 2, rNode = node * 2 + 1, mid = (l + r) / 2, ans = -INF;
    if(ql <= mid)
        ans = max(ans, get(lNode, l, mid, ql, qr));
    if(qr > mid)
        ans = max(ans, get(rNode, mid + 1, r, ql, qr));

    return ans;
}

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

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

    for(int i = 1; i <= n; i++)
    {
        l[i] = i;
        while(!s.empty() && v[i] >= v[s.top()])
        {
            l[i] = l[s.top()];
            s.pop();
        }
        s.push(i);
    }

    for(int i = 1; i <= n; i++)
    {
        //cout << "ARRAY: " << i << ' ' << l[i] - 1 << '\n';
        if(l[i] > 1)
            update(1, 1, n, l[i] - 1, v[i] + v[l[i] - 1]);
        for(auto it: q[i])
        {
            //cout << "QUERY: " << it.ind << ": " << it.l << ' ' << i << ' ' << it.k << '\n';
            //cout << get(1, 1, n, it.l, i) << "\n\n";
            bit[it.ind] = (it.k >= get(1, 1, n, it.l, i));
        }
    }

    for(int i = 1; i <= m; i++)
        cout << bit[i] << '\n';
    cout << '\n';

    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