oj.uz

Submission #128915

# Submission time Handle Problem Language Result Execution time Memory
128915 2019-07-11T10:54:43 Z OptxPrime Global Warming (CEOI18_glo) C++11
5 / 100
 36 ms 1980 KB 
#include <iostream>
#include <cmath>
#include<vector>
#include <algorithm>
#include <utility>
#include<stack>
#include<queue>
#include<map>
#include <fstream>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long

#define ans Answer
#define query Query

    int a[200010],sol[200010];
     int tail[200010];

    /*bool cmp( int x, int y )
    {
        if( x > y ) return true;
        return false;
    }*/
    /// Wa bez razloga

    int pos( int l,int r, int val )
    {
        int res=0;
            int mid=(l+r)/2;
            if( tail[mid] > val ){
                res=max(res, mid );
                l=mid+1;
            }
            else
                r=mid-1;
            return res;
    }

    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        int n,x;
        int res=0;
        cin>>n>>x;
        for( int i=1;i<=n;i++ ) cin>>a[i];
        tail[1] = a[n] + x;
        sol[n]=1;
       int len=2;
        for( int i=n-1;i>0;i-- ){
            if( a[i] + x > tail[1] ) {
                tail[1] = a[i]+x, sol[i] = 1;
            }
            else if( a[i]+x < tail[len-1] ) tail[len++]=a[i]+x, sol[i] = len-1;
            else{
                int idx = pos( 1,len-1, a[i]+x )+1;
                tail[idx] = a[i]+x;
                sol[i]=idx;
            }
        }
        res=len-1;
        for(int i=0;i<len;i++) tail[i]=0;
        tail[1]=a[1];
        len=2;

        for( int i=2;i<=n;i++ ){
            if( a[i]+x < tail[1] ) res = max( res, sol[i] ); /// ne mozemo ga ljevo nadovezat
            else if( a[i] + x > tail[len-1] ) {
                    res=max( res, len + sol[i] - 1 ) ; ///-1 jer ga racunamo dvaput
            }
            else{
                int idx = lower_bound( tail+1, tail+len, a[i]+x ) - tail;
                res=max( res, idx + sol[i] - 1 );
            }
            if( a[i] < tail[1]  ) tail[1]=a[i];
            else if( a[i] > tail[len-1] ) tail[len++]=a[i];
            else a[i] = lower_bound( tail+1, tail+len, a[i] ) - tail;

        }
        cout<<res<<endl;
      return 0;
    }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 356 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 392 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 25.0

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