제출 #1266818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266818		islam_2010	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	64 / 100	2810 ms	314396 KiB

sortbooks

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int sz = 1e6 + 5;

vector<int> st[sz << 2];
int mx[sz<<2];
int a[sz];
int n, q;

void build(int l, int r, int in){
    if(l == r){
        st[in].push_back(a[l]);
        return;
    }int mid = (l + r) >> 1;
    build(l, mid, in<<1);
    build(mid+1, r, in<<1|1);
    int i = 0, j = 0, k = 0;
    st[in].resize(st[in<<1].size()+st[in<<1|1].size());

    while(i < st[in<<1].size() && j < st[in<<1|1].size()){
        if(st[in<<1][i] < st[in<<1|1][j]){
            st[in][k++] = st[in<<1][i++];
        }else {
            st[in][k++] = st[in<<1|1][j++];
        }
    }while(i < st[in<<1].size()){
        st[in][k++] = st[in<<1][i++];
    }while(j < st[in<<1|1].size()){
        st[in][k++] = st[in<<1|1][j++];
    }if(st[in<<1].back()> st[in<<1|1][0]){
        mx[in] = st[in<<1].back() + *--lower_bound(st[in<<1|1].begin(),st[in<<1|1].end(),  st[in<<1].back());
    }mx[in] = max({mx[in], mx[in<<1], mx[in<<1|1]});

}

vector<int> v;

void getans(int ql, int qr, int l, int r, int in){
    if(l > qr || r < ql){
        return;
    }if(l >= ql && r <= qr){
        v.push_back(in);
        return;
    }int mid = (l + r) >> 1;
    getans(ql, qr, l, mid, in<<1);
    getans(ql, qr, mid+1, r, in<<1|1);
}


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }build(1, n, 1);
    while(q--){
        v.clear();
        int l, r, x;
        cin >> l >> r >> x;
        getans(l, r, 1, n, 1);
        int ans = 0, cur = 0;
        for(auto i: v){
            ans = max(ans, mx[i]);
        }for(int i = 0; i < v.size()-1; i++){
            int l = v[i], r = v[i+1];
            cur = max(cur, st[l].back());
            if(cur > st[r][0]){
                ans = max(ans,cur + *--lower_bound(st[r].begin(), st[r].end(), cur));
            }
        }if(ans <= x){
            cout << 1 << endl;
        }else {
            cout << 0 << endl;
        }
    }

}

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