oj.uz

Submission #423022

# Submission time Handle Problem Language Result Execution time Memory
423022 2021-06-10T16:01:44 Z MKopchev Financial Report (JOI21_financial) C++14
17 / 100
 2265 ms 17488 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Incorrect 0 ms 332 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Incorrect 0 ms 332 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Incorrect 0 ms 332 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1690 ms 17308 KB Output is correct
2 Correct 1691 ms 17356 KB Output is correct
3 Correct 2121 ms 17328 KB Output is correct
4 Correct 2265 ms 17444 KB Output is correct
5 Correct 1901 ms 17468 KB Output is correct
6 Correct 2052 ms 17332 KB Output is correct
7 Correct 1924 ms 17372 KB Output is correct
8 Correct 1539 ms 17336 KB Output is correct
9 Correct 1800 ms 17428 KB Output is correct
10 Correct 1553 ms 17376 KB Output is correct
11 Correct 1846 ms 17320 KB Output is correct
12 Correct 1885 ms 17488 KB Output is correct
13 Correct 2071 ms 17448 KB Output is correct
14 Correct 2185 ms 17328 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 12176 KB Output is correct
2 Correct 295 ms 12132 KB Output is correct
3 Correct 286 ms 12080 KB Output is correct
4 Correct 317 ms 12132 KB Output is correct
5 Correct 259 ms 12096 KB Output is correct
6 Correct 294 ms 12156 KB Output is correct
7 Correct 198 ms 12172 KB Output is correct
8 Correct 193 ms 12040 KB Output is correct
9 Correct 208 ms 12052 KB Output is correct
10 Correct 239 ms 12064 KB Output is correct
11 Correct 262 ms 12084 KB Output is correct
12 Correct 245 ms 12136 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Incorrect 0 ms 332 KB Output isn't correct
15 Halted 0 ms 0 KB -