Submission #466540

#	Time	Username	Problem	Language	Result	Execution time	Memory
466540		stefantaga	Financial Report (JOI21_financial)	C++14	5 / 100	732 ms	42648 KiB

Main

#include <bits/stdc++.h>

using namespace std;
int n,d,v[300005];
map <int,int> m;
int arb[1200005];
priority_queue <pair <int,int> > h[300005];
int nr;
int max1(int a,int b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}
void update (int st,int dr,int nod,int poz,int val)
{
    if (st==dr)
    {
        arb[nod]=val;
        return;
    }
    int mij=(st+dr)/2;
    if (poz<=mij)
    {
        update(st,mij,2*nod,poz,val);
    }
    else
    {
        update(mij+1,dr,2*nod+1,poz,val);
    }
    arb[nod]=max1(arb[2*nod],arb[2*nod+1]);
}
int query(int st,int dr,int nod,int ua,int ub)
{
    if (ua<=st&&dr<=ub)
    {
        return arb[nod];
    }
    int mij=(st+dr)/2,r1=0,r2=0;
    if (ua<=mij)
    {
        r1=query(st,mij,2*nod,ua,ub);
    }
    if (mij<ub)
    {
        r2=query(mij+1,dr,2*nod+1,ua,ub);
    }
    return max1(r1,r2);
}
int i,fr[300005],din[300005];
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>d;
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
        m[v[i]]=1;
    }
    nr=1;
    for (auto ind: m)
    {
        nr++;
        m[ind.first]=nr;
    }
    for (i=1;i<=n;i++)
    {
        v[i]=m[v[i]];
    }
    din[1]=1;
    h[v[1]].push({1,1});
    update(1,n+1,1,v[1],1);
    int maxim=0;
    for (i=2;i<=n;i++)
    {
        if (i-d-1>0)
        {
            fr[i-d-1]=1;
            while (!h[v[i-d-1]].empty()&&fr[h[v[i-d-1]].top().second]==1)
            {
                h[v[i-d-1]].pop();
            }
            if (!h[v[i-d-1]].empty())
            {
                 update(1,n+1,1,v[i-d-1],h[v[i-d-1]].top().first);
            }
            else
            {
                 update(1,n+1,1,v[i-d-1],0);
            }
        }
        din[i]=query(1,n+1,1,v[i],v[i]);
        din[i]=max1(din[i],query(1,n+1,1,1,v[i]-1)+1);
        h[v[i]].push({din[i],i});
        update(1,n+1,1,v[i],h[v[i]].top().first);
    }
    for (i=1;i<=n;i++)
    {
        maxim=max1(maxim,din[i]);
    }
    cout<<maxim;
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35