Submission #423039

#	Time	Username	Problem	Language	Result	Execution time	Memory
423039		MKopchev	Financial Report (JOI21_financial)	C++14	100 / 100	2348 ms	17588 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]);

    //cout<<id<<" "<<node<<" "<<l<<" "<<r<<" -> "<<tree[id][node]<<endl;
}

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;

    //cout<<"can jump "<<l<<" "<<r<<" "<<lq<<" "<<rq<<endl;

    if(lq>rq)return 1;

    //cout<<"query: "<<query(1,1,1,n,lq,rq)<<endl;

    //for(int p=lq;p<=rq;p++)cout<<query(1,1,1,n,p,p)<<" ";cout<<endl;

    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]);

    /*
    mt19937 rng(34);

    n=12;
    d=3;
    for(int i=1;i<=n;i++)inp[i]=rng()%n;
    */

    //for(int i=1;i<=n;i++)cout<<inp[i]<<" ";cout<<endl;

    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);

    //for(int i=1;i<=n-d+1;i++)cout<<mem_mini[i]<<" ";cout<<endl;

    int SZ_mini=n-d+1;

    build(1,1,1,n);

    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;

        /*
        int is=1;

        int cnt=0;

        int j;

        for(j=i-1;j>=1&&cnt<d;j--)
        {
            if(inp[i]<=inp[j])cnt++;
            else
            {
                cnt=0;

                is=max(is,dp[j]+1);
            }
        }

        cout<<"is= "<<is<<endl;

        assert(is==dp[i]);
        */

        //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:109:9: warning: unused variable 'SZ_mini' [-Wunused-variable]
  109 |     int SZ_mini=n-d+1;
      |         ^~~~~~~
Main.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     scanf("%i%i",&n,&d);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:90:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
      |                          ~~~~~^~~~~~~~~~~~~~

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