제출 #128943

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128943		OptxPrime	Global Warming (CEOI18_glo)	C++11	15 / 100	51 ms	3844 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 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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25