제출 #1285322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285322		dobri_oke	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	1349 ms	130916 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define int long long

const int N = 1e6+100;

int n, qr, a[N], ans[N], t[N * 4], mx[N * 4], z[N * 4];

struct lol{
    int r, k, pos;
};

vector < lol > q[N];

void build(int v, int l, int r){
    z[v] = -1e18;
    if(l == r){
        mx[v] = a[l];
        return;
    }
    int m = (l + r) / 2;
    build(v + v, l, m);
    build(v + v + 1, m + 1, r);
    mx[v] = max(mx[v + v], mx[v + v + 1]);
}

void push(int v, int l, int r){
    if(z[v] != -1e18){
        t[v] = max(t[v], z[v] + mx[v]);
        if(l != r){
            z[v + v] = max(z[v + v], z[v]);
            z[v + v + 1] = max(z[v + v + 1], z[v]);
        }
        z[v] = -1e18;
    }
}

void upd(int v, int l, int r, int ll, int rr, int x){
    push(v, l, r);
    if(ll <= l && r <= rr){
        z[v] = max(z[v], x);
        push(v, l, r);
        return;
    }
    if(l > rr || ll > r) return;
    int m = (l + r) / 2;
    upd(v + v, l, m, ll, rr, x);
    upd(v + v + 1, m + 1, r, ll, rr, x);
    mx[v] = max(mx[v + v], mx[v + v + 1]);
    t[v] = max(t[v + v], t[v + v + 1]);
}

int get(int v, int l, int r, int ll, int rr){
    push(v, l, r);
    if(ll <= l && r <= rr) return t[v];
    if(l > rr || ll > r) return -1e18;
    int m = (l + r) / 2;
    return max(get(v + v, l, m, ll, rr), get(v + v + 1, m + 1, r, ll, rr));
}

void solve(){
    cin >> n >> qr;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= qr; i++){
        int l, r, k;
        cin >> l >> r >> k;
        q[l].pb({r, k, i});
    }
    build(1, 1, n);
    stack < int > st;
    for(int i = n; i >= 1; i--){
        while(st.size() > 0 && a[st.top()] <= a[i]) st.pop();
        int b;
        if(st.size() > 0) b = st.top();
        else b = n + 1;
        st.push(i);
        if(i + 1 <= b - 1){
            upd(1, 1, n, i + 1, b - 1, a[i]);
        }
        for(auto [r, k, ind] : q[i]){
            ans[ind] = (get(1, 1, n, i, r) <= k);
        }
    }
    for(int i = 1; i <= qr; i++) cout << ans[i] << '\n';
}

signed main(){   
    ios_base::sync_with_stdio(0);   cin.tie(0);
    //freopen("promote.in","r",stdin);
    //freopen("promote.out","w",stdout);
    int tt=1;
   // cin >> tt;
    while(tt--){
        solve();
    }
}

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