Submission #1012983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012983		aufan	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	804 ms	159056 KiB

sortbooks

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;


int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, m;
        cin >> n >> m;

        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) cin >> a[i];

        vector<int> st;
        vector<vector<int>> v(n + 1);
        for (int i = 1; i <= n; i++) {
                while (!st.empty() && a[i] >= a[st.back()]) {
                        st.pop_back();
                }

                if (!st.empty()) {
                        v[st.back()].push_back(i);
                }

                st.push_back(i);
        }

        vector<vector<array<int, 3>>> qr(n + 1);
        for (int i = 0; i < m; i++) {
                int l, r, x;
                cin >> l >> r >> x;

                qr[l].push_back({r, x, i});
        }

        vector<int> fen(n + 1);

        auto upd = [&](int x, int val) {
                for (; x <= n; x += x & -x) fen[x] = max(fen[x], val);
        };

        auto qry = [&](int x) {
                int res = 0;
                for (; x > 0; x -= x & -x) res = max(res, fen[x]);
                return res;
        };

        vector<int> ans(m);
        for (int l = n; l >= 1; l--) {
                for (auto j : v[l]) {
                        upd(j, a[l] + a[j]);
                }

                for (auto [r, x, i] : qr[l]) {
                        ans[i] = (qry(r) <= x ? 1 : 0);
                }
        }

        for (int i = 0; i < m; i++) cout << ans[i] << '\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