Submission #494118

#	Time	Username	Problem	Language	Result	Execution time	Memory
494118		stefantaga	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1029 ms	134296 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;
int n,m,v[2000005],st[2000005],dr[2000005],cost[2000005];
vector <int> ev[2000005];
int aib[2000005],sol[2000005];
stack <int> stac;
int ub (int x)
{
    return x&(-x);
}
void update(int poz2,int x)
{
    int i;
    for (i=poz2;i<=n;i+=ub(i))
    {
        aib[i]=max(aib[i],x);
    }
}
int maxi(int poz2)
{
    int i,maxim=0;
    for (i=poz2;i>=1;i-=ub(i))
    {
        maxim=max(aib[i],maxim);
    }
    return maxim;
}
int i,j;
vector <pair <int,int>> ceau;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    for (i=1;i<=m;i++)
    {
        cin>>st[i]>>dr[i]>>cost[i];
        ev[st[i]].push_back(i);
    }
    for (i=1;i<=n;i++)
    {
        while (!stac.empty()&&v[stac.top()]<=v[i])
        {
            stac.pop();
        }
        if (!stac.empty())
        {
            ceau.push_back({stac.top(),i});
        }
        stac.push(i);
    }
    sort (ceau.begin(),ceau.end());
    int poz=((int)ceau.size())-1;
    for (i=n;i>=1;i--)
    {
        while (poz>=0&&ceau[poz].first>=i)
        {
            update(ceau[poz].second,v[ceau[poz].first]+v[ceau[poz].second]);
            poz--;
        }
        for (j=0;j<(int)ev[i].size();j++)
        {
            if (maxi(dr[ev[i][j]])<=cost[ev[i][j]])
            {
                sol[ev[i][j]]=1;
            }
        }
    }
    for (i=1;i<=m;i++)
    {
        cout<<sol[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