oj.uz

Submission #128943

# Submission time Handle Problem Language Result Execution time Memory
128943 2019-07-11T11:05:48 Z OptxPrime Global Warming (CEOI18_glo) C++11
15 / 100
 51 ms 3844 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 lo,int hi, int val )
    {
        int ans=0;
            while( lo<=hi ){
                int mid=lo + (hi-lo)/2;
                if( tail[mid] > val ){
                    ans=max( ans, mid );
                    lo=mid+1;
                }
                else hi=mid-1;
            }
            return ans;
    }

    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 3 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 348 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 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 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 3 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 348 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 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Incorrect 2 ms 376 KB Output isn't correct
15 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 3 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 348 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 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Incorrect 2 ms 376 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 2980 KB Output is correct
2 Correct 49 ms 3832 KB Output is correct
3 Correct 49 ms 3832 KB Output is correct
4 Correct 51 ms 3844 KB Output is correct
5 Correct 31 ms 3448 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1272 KB Output is correct
2 Correct 14 ms 1272 KB Output is correct
3 Correct 13 ms 1272 KB Output is correct
4 Correct 9 ms 1144 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 9 ms 1144 KB Output is correct
7 Incorrect 12 ms 1276 KB Output isn't correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 1912 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 3 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 348 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 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Incorrect 2 ms 376 KB Output isn't correct
15 Halted 0 ms 0 KB -