Submission #308794

#	Time	Username	Problem	Language	Result	Execution time	Memory
308794		nikatamliani	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2049 ms	98160 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct query{
    int index, l, k;
};
vector < query > q[N];
int n, m, a[N], L[N];
stack < int > st;
int tree[4 * N];
bool ans[N];
void update(int l, int r, int x, int v, int p) {
    if(l > x || r < x) return;
    if(l == r) {
        tree[p] = max(tree[p], v);
    } else {
        int m = l + r >> 1;
        update(l, m, x, v, p << 1);
        update(m + 1, r, x, v, p << 1 | 1);
        tree[p] = max(tree[p << 1], tree[p << 1 | 1]);
    }
}
int cnt(int l, int r, int L, int R, int p) {
    if(L > r || l > R) return 0;
    if(L <= l && R >= r) return tree[p];
    int m = l + r >> 1;
    return max(cnt(l, m, L, R, p << 1), cnt(m + 1, r, L, R, p << 1 | 1));
}
int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) scanf("%d", a + i);
    for(int i = 1; i <= m; ++i) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        q[r].push_back({i, l, k});
    }
    for(int i = 1; i <= n; ++i) {
        while(!st.empty() && a[st.top()] <= a[i]) st.pop();
        if(!st.empty()) {
            L[i] = st.top();
        }
        st.push(i);
    }
    for(int r = 1; r <= n; ++r) {
        if(L[r] > 0) {
            update(1, n, L[r], a[r] + a[L[r]], 1);
        }
        for(auto [index, l, k] : q[r]) {
            ans[index] = cnt(1, n, l, r, 1) <= k; 
        }
    }
    for(int i = 1; i <= m; ++i) {
        printf("%d\n", ans[i]);
    }
}

Compilation message (stderr)

sortbooks.cpp: In function 'void update(int, int, int, int, int)':
sortbooks.cpp:17:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |         int m = l + r >> 1;
      |                 ~~^~~
sortbooks.cpp: In function 'int cnt(int, int, int, int, int)':
sortbooks.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int m = l + r >> 1;
      |             ~~^~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:48:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |         for(auto [index, l, k] : q[r]) {
      |                  ^
sortbooks.cpp:31:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |     for(int i = 1; i <= n; ++i) scanf("%d", a + i);
      |                                 ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |         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