Submission #147808

#	Time	Username	Problem	Language	Result	Execution time	Memory
147808		theboatman	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	17 / 100	3024 ms	28712 KiB

sortbooks

#include <bits/stdc++.h>

#define y1 theboatman
#define make_struct(args...) {args}

using namespace std;

typedef long long ll;

const long long INF = 1e18 + 10;
const int inf = 1e9 + 10;
const int N = 1e6 + 10;

struct osu {
    int l, r, k;
};

struct osu1 {
    int l, r, x;
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;

    vector <int> a(n);
    for(auto &i : a) {
        cin >> i;
    }

    vector <int> st;
    vector <osu1> c;
    for(int i = 0; i < n; i++) {
        while(st.size() && a[st.back()] <= a[i]) {
            st.pop_back();
        }

        if (st.size()) {
            c.push_back(make_struct(st.back(), i, a[i] + a[st.back()]));
        }

        st.push_back(i);
    }

    vector <osu> b(m);
    for(auto &i : b) {
        cin >> i.l >> i.r >> i.k;
        i.l--, i.r--;

        int mx = -inf;
        for(auto j : c) {
            if (i.l <= j.l && j.r <= i.r) {
                mx = max(mx, j.x);
            }
        }

        cout << (mx <= i.k) << "\n";
    }

    return 0;
}

/*
*/

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23