Submission #348643

#	Time	Username	Problem	Language	Result	Execution time	Memory
348643		parsabahrami	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1823 ms	68932 KiB

sortbooks

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
#define lc                          id << 1
#define rc                          lc | 1

const int N = 1e6 + 10, MOD = 1e9 + 7;
int seg[N << 2], R[N], A[N], n, q; stack<int> st; vector<pair<pii, int>> Q[N];

void modify(int pos, int x, int id = 1, int l = 1, int r = n + 1) {
    if (r - l < 2) {
        seg[id] = max(seg[id], x);
        return;
    }
    int mid = (l + r) >> 1;
    if (pos < mid) modify(pos, x, lc, l, mid);
    else modify(pos, x, rc, mid, r);
    seg[id] = max(seg[lc], seg[rc]);
}

int get(int ql, int qr, int id = 1, int l = 1, int r = n + 1) {
    if (qr <= l || r <= ql) return -MOD;
    if (ql <= l && r <= qr) return seg[id];
    int mid = (l + r) >> 1;
    return max(get(ql, qr, lc, l, mid), get(ql, qr, rc, mid, r));
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
    for (int i = 1; i <= q; i++) {
        int l, r, k; scanf("%d%d%d", &l, &r, &k);
        Q[r].push_back({{l, k}, i});
    }
    for (int i = 1; i <= n; i++) {
        while (SZ(st) && A[st.top()] <= A[i]) st.pop();
        if (SZ(st)) modify(st.top(), A[i] + A[st.top()]);
        st.push(i);
        for (auto j : Q[i]) {
            R[j.S] = get(j.F.F, i + 1) <= j.F.S;
        }
    }
    for (int i = 1; i <= q; i++) printf("%d\n", R[i]);
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:38:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |     for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
      |                                  ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:40:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |         int l, r, k; scanf("%d%d%d", &l, &r, &k);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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