Submission #128930

#	Time	Username	Problem	Language	Result	Execution time	Memory
128930		OptxPrime	Global Warming (CEOI18_glo)	C++11	5 / 100	36 ms	2680 KiB

glo

#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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25