Submission #717770

#	Time	Username	Problem	Language	Result	Execution time	Memory
717770		TS_2392	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1393 ms	97724 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
int n, numq, a[N], st[N * 4], prv[N];
bool res[N];
vector< array<int, 3> > qrywithR[N];
void update(int id, int L, int R, int p, int v){
    if(L == R){
        st[id] = max(st[id], v);
        return;
    }
    int mid = L + R >> 1;
    if(p <= mid) update(id << 1, L, mid, p, v);
    else update(id << 1 | 1, mid + 1, R, p, v);
    st[id] = max(st[id << 1], st[id << 1 | 1]);
}
int get_max(int id, int L, int R, int Lq, int Rq){
    if(R < Lq || Rq < L) return 0;
    if(Lq <= L && R <= Rq) return st[id];
    int mid = L + R >> 1;
    return max(get_max(id << 1, L, mid, Lq, Rq), get_max(id << 1 | 1, mid + 1, R, Lq, Rq));
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> numq;
    a[0] = 1e9 + 3;
    for(int i = 1, j; i <= n; ++i){
        cin >> a[i]; j = i - 1;
        while(a[j] <= a[i]) j = prv[j];
        prv[i] = j;
    }
    for(int i = 1; i <= numq; ++i){
        int l, r, k;
        cin >> l >> r >> k;
        qrywithR[r].push_back({l, k, i});
    }
    for(int i = 1; i <= n; ++i){
        update(1, 0, n, prv[i], a[i] + a[prv[i]]);
        for(auto &x : qrywithR[i]){
            int j = x[0], k = x[1], id = x[2];
            if(get_max(1, 0, n, j, i) <= k) res[id] = 1;
            else res[id] = 0;
        }
    }
    for(int i = 1; i <= numq; ++i){
        cout << res[i] << '\n';
    }
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'void update(int, int, int, int, int)':
sortbooks.cpp:12:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |     int mid = L + R >> 1;
      |               ~~^~~
sortbooks.cpp: In function 'int get_max(int, int, int, int, int)':
sortbooks.cpp:20:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |     int mid = L + R >> 1;
      |               ~~^~~

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