제출 #492412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
492412		infertechno2	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3060 ms	33104 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Size=1e6+1;

ll w[Size],min_tree[4*Size],max_tree[4*Size];

void update(ll l,ll r,ll i,bool min_or_max,ll val){
    if(l==r){
        if(min_or_max){
            min_tree[i]=val;
        }else{
            max_tree[i]=val;
        }
    }else{
        ll mid=(l+r)/2;
        update(l,mid,i*2,min_or_max,val);
        update(mid+1,r,i*2+1,min_or_max,val);
        min_or_max ? min_tree[i]=min(min_tree[i*2],min_tree[i*2+1]) : max_tree[i]=max(max_tree[i*2],max_tree[i*2+1]);
    }
}
ll query(ll l,ll r,ll i,ll tl,ll tr,bool min_or_max){
    if(l>tr or r<tl){
        return -1;
    }
    if(l==r){
        if(min_or_max){
            return min_tree[i];
        }else{
            return max_tree[i];
        }
    }else{
        ll mid=(l+r)/2;
        ll n1=query(l,mid,i*2,tl,min(tr,mid),min_or_max);
        ll n2=query(mid+1,r,i*2+1,max(tl,mid+1),tr,min_or_max);
        if(n1==-1)return n2;
        if(n2==-1)return n1;
        if(min_or_max){
            return min(n1,n2);
        }else{
            return max(n1,n2);
        }
    }
}



void solve(){
    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<n;i++){
        cin>>w[i];
        update(0,n-1,1,false,w[i]);
        update(0,n-1,1,true,w[i]);
    }
    while(m--){
        ll l,r,k;
        cin>>l>>r>>k;
        l--; r--;
        ll low=query(0,n-1,1,l,r,true),high=query(0,n-1,1,l,r,false);
        cout<<(low+high<=k)<<endl;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    while(t--){
        solve();
    }
    return 0;
}

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