oj.uz

Submission #223091

# Submission time Handle Problem Language Result Execution time Memory
223091 2020-04-14T17:52:59 Z MKopchev Global Warming (CEOI18_glo) C++14
0 / 100
 354 ms 7672 KB 
#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42;

int n,x,inp[nmax];

int tree[4*nmax];
void update(int node,int l,int r,int pos,int val)
{
    if(l==r)
    {
        tree[node]=val;
        return;
    }
    int av=(l+r)/2;

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

    tree[node]=max(tree[node*2],tree[node*2+1]);
}
int query(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return tree[node];
    int av=(l+r)/2,ret=0;

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

    return ret;
}

int sorted_inp[nmax];

int longest_to_end[nmax];

int main()
{
    scanf("%i%i",&n,&x);

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

    int output=0;

    for(int i=n;i>=1;i--)
    {
        int pos_up=upper_bound(sorted_inp+1,sorted_inp+n+1,inp[i])-sorted_inp;

        int pos_low=lower_bound(sorted_inp+1,sorted_inp+n+1,inp[i])-sorted_inp;

        if(pos_up<=n)longest_to_end[i]=query(1,1,n,pos_up,n);

        longest_to_end[i]++;

        output=max(output,longest_to_end[i]);

        update(1,1,n,pos_low,longest_to_end[i]);

        //cout<<i<<" -> "<<longest_to_end[i]<<endl;
    }

    for(int i=0;i<4*nmax;i++)tree[i]=0;

    for(int i=1;i<=n;i++)
    {
        //try to add
        int pos_add=lower_bound(sorted_inp+1,sorted_inp+n+1,inp[i]+x)-sorted_inp;
        pos_add--;

        if(pos_add)
        {
            output=max(output,query(1,1,n,1,pos_add)+longest_to_end[i]);
            //cout<<i<<" -> "<<query(1,1,n,1,pos_add)<<" "<<longest_to_end[i]<<endl;
        }

        int pos=lower_bound(sorted_inp+1,sorted_inp+n+1,inp[i])-sorted_inp;
        pos--;

        int current=0;

        if(pos)current=query(1,1,n,pos,n);

        current++;

        update(1,1,n,pos,current);
    }

    printf("%i\n",output);
    return 0;
}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&x);
     ~~~~~^~~~~~~~~~~~~~
glo.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&inp[i]);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 354 ms 7672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 4472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 5564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -