Submission #944049

#	Time	Username	Problem	Language	Result	Execution time	Memory
944049		boyliguanhan	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	677 ms	61008 KiB

sortbooks

//upsolved after reading other's code
#include<bits/stdc++.h>
#define X s.top()
#define K 1<<20
using namespace std;
vector<tuple<int,int,int>>q[1<<20];
int n,a[1<<20],t[1<<20],m,r[1<<20];
void upd(int x,int v){
    for(;x;x-=x&-x)
        t[x]=max(t[x],v);
}
int qu(int x){
    int v=0;
    for(;x<=n;x+=x&-x)
        v=max(t[x],v);
    return v;
}
stack<int>s;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    a[0]=2e9,s.push(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=0,a,b,c;i<m;i++)
        cin>>a>>b>>c,q[b].push_back({a,c,i});
    for(int i=1;i<=n;i++){
        while(a[X]<=a[i])
            s.pop();
        if(X) upd(X,a[X]+a[i]);
        s.push(i);
        for(auto[a,b,c]:q[i])
            r[c]=qu(a)<=b;
    }
    for(int i=0;i<m;i++)
        cout<<r[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