제출 #1165640

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

sortbooks

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct segtree{
    vector<int>d;
    segtree(int n){
        d.resize(4*n);
    }
    int query(int v,int l,int r,int L,int R){
        if(R<L||R<l||r<L) return 0;
        if(L<=l&&r<=R) return d[v];
        int m=(l+r)>>1;
        return max(query(v<<1,l,m,L,R),query(v<<1|1,m+1,r,L,R));
    }
    void update(int v,int l,int r,int pos,int val){
        if(r<pos||pos<l) return;
        if(l==r){
            d[v]=val;
            return;
        }
        int m=(l+r)>>1;
        update(v<<1,l,m,pos,val);
        update(v<<1|1,m+1,r,pos,val);
        d[v]=max(d[v<<1],d[v<<1|1]);
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,m;
    cin>>n>>m;
    int a[n+5];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    vector<array<int,3>>ask[n+5];
    for(int i=1;i<=m;i++){
        int l,r,k;
        cin>>l>>r>>k;
        ask[l].pb({i,r,k});
    }
    int b[m+5];
    stack<int>s;
    segtree sg(n);
    for(int i=n;i>=1;i--){
        while(!s.empty()&&a[s.top()]<a[i]){
            sg.update(1,1,n,s.top(),a[s.top()]+a[i]);
            s.pop();
        }
        for(auto [j,r,k]:ask[i]){
            b[j]=(sg.query(1,1,n,i,r)<=k?1:0);
        }
        s.push(i);
    }
    for(int i=1;i<=m;i++){
        cout<<b[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