Submission #344162

#	Time	Username	Problem	Language	Result	Execution time	Memory
344162		Nurlykhan	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1694 ms	73712 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e6 + 10;
const int K = 450;

int n, m;
int w[N];

int ans[N];
int L[N], R[N], k[N];
vector<int> query[N];

int suff_w[N], suff_mood[N];

void solve(int l = 0, int r = n - 1) {
    if (l == r)
        return;
    int mid = (l + r) / 2;

    // 5 4 100
    vector<int> s; // TODO: replace set with fenwick
    suff_w[mid + 1] = suff_mood[mid + 1] = 0;
    for (int i = mid; i >= l; i--) {
        suff_w[i] = max(suff_w[i + 1], w[i]);
        suff_mood[i] = suff_mood[i + 1];

        while (!s.empty() && s.back() < w[i]) {
            suff_mood[i] = max(suff_mood[i], s.back() + w[i]);
            s.pop_back();
        }

        if (s.empty() || s.back() > w[i])
            s.push_back(w[i]);
    }

    s.clear();
    int mx = 0, mxx = 0;
    for (int i = mid + 1; i <= r; i++) {
        if (mxx <= w[i]) {
            mxx = w[i];
            s.push_back(w[i]);
        } else {
            mx = max(mx, mxx + w[i]);
        }


        // TODO: optimize iteration over queries
        for (auto j : query[i]) {
            if (L[j] >= l && L[j] <= mid) {
                int cur_mx = max(suff_mood[L[j]], mx);

                int tmp = suff_w[L[j]];
                int it = lower_bound(s.begin(), s.end(), tmp) - s.begin() - 1;
                if (it >= 0) {
                    cur_mx = max(cur_mx, s[it] + tmp);
                }

                if (k[j] >= cur_mx) {
                    ans[j] = 1;
                } else {
                    ans[j] = 0;
                }
            }
        }
    }

    solve(l, mid);
    solve(mid + 1, r);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &w[i]);
    }

    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &L[i], &R[i], &k[i]);
        --L[i], --R[i];
        query[R[i]].push_back(i);
    }

    solve();

    for (int i = 0; i < m; i++) {
        if (L[i] == R[i]) ans[i] = 1;
        printf("%d\n", ans[i]);
    }
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |         scanf("%d", &w[i]);
      |         ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |         scanf("%d%d%d", &L[i], &R[i], &k[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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