Submission #1086663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086663		maxFedorchuk	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1420 ms	116392 KiB

sortbooks

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

const long long MX=1e6+10;

vector < pair < long long , pair < long long , long long > > > zap[MX];
long long a[MX],ans[MX],fen[MX],n,q;


long long get_real_in(long long in)
{
    return (n-in+1);
}

long long fget(long long in)
{
    in=get_real_in(in);

    long long ans=0;
    while(in>0)
    {
        ans=max(ans,fen[in]);
        in=(in&(in+1))-1;
    }

    return ans;
}

void upd(long long in,long long zn)
{
    in=get_real_in(in);

    while(in<=n)
    {
        fen[in]=max(fen[in],zn);
        in=(in|(in+1));
    }
}

int main()
{
    cin>>n>>q;

    for(long long i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    for(long long i=1;i<=q;i++)
    {
        long long l,r,w;
        cin>>l>>r>>w;
        zap[r].push_back({l,{w,i}});
    }


    stack < long long > st; // pos

    for(long long i=1;i<=n;i++)
    {
        while(!st.empty())
        {
            if(a[st.top()]<=a[i])
            {
                st.pop();
            }
            else
            {
                break;
            }
        }

        if(!st.empty())
        {
            long long pos=st.top();

            upd(pos,a[pos]+a[i]);
        }

        for(auto u:zap[i])
        {
            ans[u.second.second]=(fget(u.first)<=u.second.first);
        }

        st.push(i);
    }


    for(long long i=1;i<=q;i++)
    {
        cout<<ans[i]<<"\n";
    }

    return 0;
}

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