Submission #602290

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
602290	2022-07-22T20:47:26 Z	Ozy	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	1022 ms	66416 KB

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
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Incorrect	1 ms	340 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Incorrect	1 ms	340 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1022 ms	59352 KB	Output is correct
2	Correct	667 ms	62520 KB	Output is correct
3	Correct	705 ms	62344 KB	Output is correct
4	Correct	700 ms	62596 KB	Output is correct
5	Incorrect	811 ms	66416 KB	Output isn't correct
6	Halted	0 ms	0 KB	-