제출 #1285347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285347		dobri_oke	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	1626 ms	106868 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], z[N * 4];

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

vector < lol > q[N];

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

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] += 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);
    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});
    }
    stack < int > st;
    for(int i = n; i >= 1; i--){
        while(st.size() > 0 && a[st.top()] < a[i]) {
            int b = st.top(), bb;
            st.pop();
            if(st.size() == 0) bb = n + 1;
            else bb = st.top();
            upd(1, 1, n, b + 1, bb - 1, a[i] - a[b]);
            upd(1, 1, n, b, b, a[i] + a[b]);
        }
        st.push(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: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23