Submission #344148

#	Time	Username	Problem	Language	Result	Execution time	Memory
344148		Nurlykhan	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3066 ms	112336 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
    set<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];

        auto it = s.lower_bound(w[i]);
        if (it != s.begin()) {
            it--;
            suff_mood[i] = max(suff_mood[i], *it + w[i]);
        }

        s.insert(w[i]);
    }

    s.clear();
    int mx = 0, mxx = 0;
    for (int i = mid + 1; i <= r; i++) {
        if (mxx <= w[i]) {
            mxx = w[i];
        } else {
            mx = max(mx, mxx + w[i]);
        }
        s.insert(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]];
                auto it = s.lower_bound(tmp);
                if (it != s.begin()) {
                    it--;
                    cur_mx = max(cur_mx, *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: 0 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 0 / 23