Submission #206693

#	Time	Username	Problem	Language	Result	Execution time	Memory
206693		brcode	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3023 ms	78992 KiB

sortbooks

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1e6+5;
long long segmax[4*MAXN];
long long segmin[4*MAXN];
long long ans[4*MAXN];
long long arr[MAXN];
void build(long long curr,long long l,long long r){
    if(l==r){
        segmax[curr] = arr[l];
        segmin[curr] = arr[r];
        ans[curr] = 0;
        return;
        
    }
    long long mid = (l+r)/2;
    build(2*curr,l,mid);
    build(2*curr+1,mid+1,r);
    segmax[curr] = max(segmax[2*curr],segmax[2*curr+1]);
    segmin[curr] = min(segmin[2*curr],segmin[2*curr+1]);
    long long tempans = 0;
    if(segmax[2*curr]>segmin[2*curr+1]){
        tempans = segmax[2*curr]+segmin[2*curr+1];
    }
    
    ans[curr] = max(max(ans[2*curr],ans[2*curr+1]),tempans);

}
pair<long long,pair<long long,long long>> query(long long curr,long long l,long long r,long long tl,long long tr){
    if(l>tr||r<tl){
        pair<long long,pair<long long,long long>> hold;
        hold.first = -1;
        hold.second.second = 0;
        hold.second.second = 0;
        return hold;
    }
    if(l>=tl && r<=tr){
        pair<long long,pair<long long,long long>> hold;
      //  cout<<l<<" "<<r<<" "<<ans[curr]<<endl;
        hold.first = ans[curr];
        hold.second.first = segmax[curr];
        hold.second.second = segmin[curr];
        return hold;
    }
    long long mid = (l+r)/2;
    auto holdfirst = query(2*curr,l,mid,tl,tr);
    auto holdsecond = query(2*curr+1,mid+1,r,tl,tr);
    pair<long long,pair<long long,long long>> tempans;
   // cout<<l<<" "<<r<<" "<<holdfirst.first<<" "<<holdsecond.second.second<<endl;
    tempans.first = 0;
    if(holdfirst.second.first>holdsecond.second.second && holdfirst.second.first!=0 && holdsecond.second.second!=0){
        tempans.first = holdfirst.second.first+holdsecond.second.second;
    }
   // cout<<l<<" "<<r<<" "<<tempans.first<<endl;
    tempans.first =max(max(holdfirst.first,holdsecond.first),tempans.first);
    
    tempans.second.first=max(holdfirst.second.first,holdsecond.second.first);
    if(holdfirst.second.second == 0){
        tempans.second.second = holdsecond.second.second;
    }else if(holdsecond.second.second == 0){
        tempans.second.second = holdfirst.second.second;
    }else{
        tempans.second.second = min(holdfirst.second.second,holdsecond.second.second) ;
    }

    return tempans;
}
int main() {
    long long n,m;
    cin>>n>>m;
    for(long long i=1;i<=n;i++){
        cin>>arr[i];
    }
    build(1,1,n);
    for(long long i=1;i<=m;i++){
        long long l,r,k;
        cin>>l>>r>>k;
      //  cout<<l<<" "<<r<<" "<<query(1,1,n,l,r).first<<endl;
        if(query(1,1,n,l,r).first>k){
            cout<<0<<endl;
        }else{
            cout<<1<<endl;
        }
    }
}

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