Submission #206794

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

sortbooks

#include <iostream>
#include <bits/stdc++.h>


using namespace std;
const long long MAXN = 1e6+1;
long long seg[4*MAXN];
long long n,m;

long long l[MAXN];
long long r[MAXN];
vector<vector<long long>> v1(MAXN);
long long arr[MAXN];
long long k[MAXN];
long long pos[MAXN];
long long ans[MAXN];
void update(long long curr,long long l,long long r,long long ind,long long val){
    if(l==r){
        seg[curr] = val;
        return;
    }
    long long mid = (l+r)/2;
    if(ind<=mid){
        update(2*curr,l,mid,ind,val);
    }else{
        update(2*curr+1,mid+1,r,ind,val);
    }
    seg[curr] = max(seg[2*curr],seg[2*curr+1]);
}
long long query(long long curr,long long l,long long r,long long tl,long long tr){
    if(l>tr||r<tl){
        return 0;
    }
    if(l<=tl && r<=tr){
        return seg[curr];
    }
    long long mid = (l+r)/2;
    return max(query(2*curr,l,mid,tl,tr),query(2*curr+1,mid+1,r,tl,tr));
}
int main() {
    cin>>n>>m;
    for(long long i=1;i<=n;i++){
        cin>>arr[i];
        pos[i] = i-1;
        while(pos[i] && arr[pos[i]]<=arr[i]){
            pos[i] = pos[pos[i]];
        }
    }
    for(long long i=1;i<=m;i++){
        cin>>l[i]>>r[i]>>k[i];
        v1[r[i]].push_back(i);
    }
    for(long long i=1;i<=n;i++){
        if(pos[i]){
            update(1,1,n,pos[i],arr[i]+arr[pos[i]]);
            
        }
        for(long long x:v1[i]){
                ans[x]=(query(1,1,n,l[x],r[x])<=k[x]);
            }
        
    }
    for(long long i=1;i<=m;i++){
        cout<<ans[i]<<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