Submission #1112302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112302		Icelast	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1088 ms	109384 KiB

sortbooks

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct SegmentTree{
    struct Node{
        ll mx = 0;
    };
    vector<Node> T;
    int n, N;
    SegmentTree(int n) : n(n){
        N = 1;
        while(N < n) N*=2;
        T.resize(N*2+1);
    };
    void upd(int i, ll x){
        auto upd = [&](auto upd, int node, int low, int high, int i, ll x) -> void{
            if(low == high){
                T[node].mx = max(T[node].mx, x);
                return;
            }
            int mid = (low+high)/2;
            if(i <= mid){
                upd(upd, node*2, low, mid, i, x);
            }else{
                upd(upd, node*2+1, mid+1, high, i, x);
            }
            T[node].mx = max(T[node*2].mx, T[node*2+1].mx);
        };
        upd(upd, 1, 1, N, i, x);
    }
    ll get_max(int l, int r){
        auto get_max = [&](auto get_max, int node, int low, int high, int l, int r) -> ll{
            if(low > r || l > high) return 0;
            if(low >= l && r >= high) return T[node].mx;
            int mid = (low+high)/2;
            return max(get_max(get_max, node*2, low, mid, l, r), get_max(get_max, node*2+1, mid+1, high, l, r));
        };
        return get_max(get_max, 1, 1, N, l, r);
    }
};
struct que{
    int l, r, k, id;
};
void solve(){
    int n, Q;
    cin >> n >> Q;
    vector<int> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    vector<vector<que>> sweep(n+1);
    for(int i = 1; i <= Q; i++){
        int l, r, k, id;
        cin >> l >> r >> k;
        id = i;
        sweep[r].push_back({l, r, k, id});
    }
    stack<int> st;
    SegmentTree T(n+1);
    vector<int> ans(Q+1);
    for(int i = 1; i <= n; i++){
        while(!st.empty() && a[st.top()] <= a[i]) st.pop();
        if(!st.empty()){
            T.upd(st.top(), a[st.top()]+a[i]);
        }
        for(auto it : sweep[i]){
            ans[it.id] = T.get_max(it.l, it.r) <= it.k;
        }
        st.push(i);
    }
    for(int i = 1; i <= Q; i++){
        cout << ans[i] << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    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