Submission #423022

#	Time	Username	Problem	Language	Result	Execution time	Memory
423022		MKopchev	Financial Report (JOI21_financial)	C++14	17 / 100	2265 ms	17488 KiB

Main

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

const int nmax=3e5+42,inf=1e9+42;

int n,d,inp[nmax];

int dp[nmax];

int tree[3][4*nmax];

int mem_mini[nmax];

void build(int id,int node,int l,int r)
{
    if(l==r)
    {
        if(id==0)tree[id][node]=-inp[l];
        else tree[id][node]=mem_mini[l];

        return;
    }

    int av=(l+r)/2;

    build(id,node*2,l,av);
    build(id,node*2+1,av+1,r);

    tree[id][node]=max(tree[id][node*2],tree[id][node*2+1]);
}

bool cmp(int a,int b)
{
    if(inp[a]!=inp[b])return inp[a]<inp[b];

    return a>b;
}

int query(int id,int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return tree[id][node];

    int av=(l+r)/2;

    int ret=-inf;

    if(lq<=av)ret=max(ret,query(id,node*2,l,av,lq,min(av,rq)));
    if(av<rq)ret=max(ret,query(id,node*2+1,av+1,r,max(av+1,lq),rq));

    return ret;
}

void update(int id,int node,int l,int r,int pos,int val)
{
    if(l==r)
    {
        tree[id][node]=val;
        return;
    }

    int av=(l+r)/2;

    if(pos<=av)update(id,node*2,l,av,pos,val);
    else update(id,node*2+1,av+1,r,pos,val);

    tree[id][node]=max(tree[id][node*2],tree[id][node*2+1]);
}

bool can_jump(int l,int r)
{
    int lq=l;
    int rq=r-d;

    if(lq>rq)return 1;

    return query(1,1,1,n,lq,rq)<inp[r];
}
int main()
{
    scanf("%i%i",&n,&d);

    for(int i=1;i<=n;i++)scanf("%i",&inp[i]);

    build(0,1,1,n);

    for(int i=1;i<=n-d+1;i++)
        mem_mini[i]=-query(0,1,1,n,i,i+d-1);

    int SZ_mini=n-d+1;

    build(1,1,1,SZ_mini);

    vector<int> order={};

    for(int i=1;i<=n;i++)order.push_back(i);

    sort(order.begin(),order.end(),cmp);

    int outp=0;

    for(auto i:order)
    {
        int ok=i,not_ok=0;

        while(ok-not_ok>1)
        {
            int av=(ok+not_ok)/2;

            if(can_jump(av,i))ok=av;
            else not_ok=av;
        }

        dp[i]=query(2,1,1,n,ok,i)+1;

        outp=max(outp,dp[i]);

        update(2,1,1,n,i,dp[i]);

        //cout<<i<<" -> "<<dp[i]<<" ok= "<<ok<<endl;

        //for(int j=1;j<=n;j++)cout<<query(2,1,1,n,j,j)<<" ";cout<<endl;
    }

    printf("%i\n",outp);

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     scanf("%i%i",&n,&d);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:82:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
      |                          ~~~~~^~~~~~~~~~~~~~

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