제출 #1305170

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305170		Warinchai	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	927 ms	90508 KiB

sortbooks

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

int ar[1000005];
vector<pair<pair<int,int>,int>>q[1000005];
int ans[1000005];

struct segtree{
    int info[4000005];
    void upd(int st,int en,int i,int pos,int val){
        if(st>pos||en<pos)return;
        if(st==en)return info[i]=max(info[i],val),void();
        int m=(st+en)/2;
        upd(st,m,i*2,pos,val);
        upd(m+1,en,i*2+1,pos,val);
        info[i]=max(info[i*2],info[i*2+1]);
    }
    int fans(int st,int en,int i,int l,int r){
        if(st>r||en<l)return 0;
        if(st>=l&&en<=r)return info[i];
        int m=(st+en)/2;
        return max(fans(st,m,i*2,l,r),fans(m+1,en,i*2+1,l,r));
    }
    void build(int st,int en,int i){
        info[i]=0;
        if(st==en)return;
        int m=(st+en)/2;
        build(st,m,i*2);
        build(m+1,en,i*2+1);
    }
}tr;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>ar[i];
    tr.build(1,n,1);
    for(int i=1;i<=m;i++){
        int l,r,k;cin>>l>>r>>k;
        q[r].push_back({{l,k},i});
    }
    stack<int>s;
    for(int i=1;i<=n;i++){
        while(!s.empty()&&ar[s.top()]<=ar[i])s.pop();
        if(!s.empty())tr.upd(1,n,1,s.top(),ar[s.top()]+ar[i]);
        for(auto [x,id]:q[i]){
            if(tr.fans(1,n,1,x.first,i)<=x.second)ans[id]=1;
        }
        s.push(i);
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
}

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