Submission #993274

#	Time	Username	Problem	Language	Result	Execution time	Memory
993274		simona1230	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1750 ms	75440 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

long long n,m,a[1000001];

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

int p[1000001];

void prec()
{
    stack<int> s;
    for(int i=1;i<=n;i++)
    {
        while(s.size()&&a[s.top()]<=a[i])
            s.pop();

        if(s.size())
            p[i]=s.top();
        s.push(i);
    }
}

struct query
{
    int l,r,k,i;
    query(){}
    query(int _l,int _r,int _k,int _i)
    {
        l=_l;
        r=_r;
        k=_k;
        i=_i;
    }

    bool operator<(const query&q)const
    {
        return r<q.r;
    }
};
query q[1000001];
int f[1000001];
int t[4000001];

void update(int i,int l,int r,int idx,int val)
{
    if(l==r)
    {
        t[i]=max(t[i],val);
        return;
    }

    int md=(l+r)/2;
    if(idx<=md)update(i*2,l,md,idx,val);
    else update(i*2+1,md+1,r,idx,val);

    t[i]=max(t[i*2],t[i*2+1]);
}

int query(int i,int l,int r,int ql,int qr)
{
    if(ql>qr)return 0;
    if(ql<=l&&r<=qr)return t[i];
    int md=(l+r)/2;
    return max(query(i*2,l,md,ql,min(md,qr)),query(i*2+1,md+1,r,max(md+1,ql),qr));
}


void solve()
{
    for(int i=1;i<=m;i++)
    {
        int l,r,k;
        cin>>l>>r>>k;
        q[i]={l,r,k,i};
    }
    sort(q+1,q+m+1);

    for(int i=1;i<=m;i++)
    {
        for(int j=q[i-1].r+1;j<=q[i].r;j++)
            if(p[j])update(1,1,n,p[j],a[p[j]]+a[j]);

        int ans=query(1,1,n,q[i].l,q[i].r);
        if(ans<=q[i].k)f[q[i].i]=1;
        else f[q[i].i]=0;
    }

    for(int i=1;i<=m;i++)
        cout<<f[i]<<endl;
}

int main()
{
    speed();
    read();
    prec();
    solve();

    return 0;
}
/*
5 0
11 5 4 10 8
*/

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