Submission #602296

#	Time	Username	Problem	Language	Result	Execution time	Memory
602296		Ozy	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	902 ms	96116 KiB

sortbooks

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 1000000

lli n,q,apu,a;
lli w[MAX+2],l[MAX+2],r[MAX+2],k[MAX+2],res[MAX+2];
lli finales[MAX+2];

stack<lli> monotone;
lli dsu[MAX+2],M[MAX+2];

lli sube(lli a) {

    if (dsu[a] == a) return a;
    lli x = sube(dsu[a]);
    M[a] = max(M[dsu[a]], M[a]);
    dsu[a] = x;
    return dsu[a];

}

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

    cin >> n >> q;
    rep(i,1,n) cin >> w[i];
    rep(i,1,q) cin >> l[i] >> r[i] >> k[i];
    iota(finales+1, finales+q+1, 1);

    sort(finales+1, finales+q+1, [&] (lli a, lli b) {
        return r[a] < r[b];
    });
    iota(dsu+1,dsu+n+1,1);

    apu = 1;
    rep(i,1,n) {

        while (!monotone.empty() && w[monotone.top()] <= w[i]) {
            dsu[monotone.top()] = i;
            monotone.pop();
        }
        if (!monotone.empty()) M[monotone.top()] = w[monotone.top()] + w[i];
        monotone.push(i);

        while (apu <= q && r[finales[apu] ] == i) {
            a = sube( l[finales[apu]] );
            a = M[l[finales[apu]]];
            if (a <= k[finales[apu]]) res[finales[apu]] = 1;
            apu++;
        }

    }

    rep(i,1,q) cout << res[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