Submission #128442

#	Time	Username	Problem	Language	Result	Execution time	Memory
128442		OptxPrime	Global Warming (CEOI18_glo)	C++11	0 / 100	32 ms	3128 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[100010],big[100010],small[100010],smallpos[100010],bigpos[100010];
     int tail[100010];

    /*bool cmp( int x, int y )
    {
        if( x > y ) return true;
        return false;
    }*/
    int uupper_bound( 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 sol=0;
        cin>>n>>x;
        for( int i=0;i<n;i++ ){
            cin>>a[i+1];
            big[i+1]=a[i+1]+x;
            small[i+1]=a[i+1]-x;
        }

        tail[1]=a[1];
        int len=2;
        bigpos[1] = 1;
        bigpos[2]=1;
        if( big[2] > a[1] ) bigpos[2]=2;        /// valja li ovo

        for( int i=2;i<=n;i++ ){
            if( a[i] < tail[1] )    tail[1] = a[i];
            else if( a[i] > tail[len-1] ) tail[len++]=a[i];
            else{
                int idx = lower_bound( tail+1, tail+len, a[i] )-tail;
                tail[idx]=a[i];
            }
         //   if( i==2 ) cout << len << " " << tail[len-1] << " "<< big[i+1] << " majsta " <<endl;
            ///provjeriti valja li ova bigpos racunaljka
            if( big[i+1] < tail[1] ) bigpos[i+1]=1;
            else if(big[i+1] > tail[len-1] ) bigpos[i+1]=len;
            else bigpos[i+1] = lower_bound( tail+1, tail+len,big[i+1] )-tail;
        }   ///izgradili smo regular. smallpos[n-1] i smallpos[n] moram rucno naci, i isto za bigpos
        sol=len-1; /// ovo je prvo rjesenje kad ne dodas nista

        bigpos[n+1]=0;

        for( int i=0;i<len;i++ ) tail[i]=0;
        tail[1]=a[n];
        len=2;
        smallpos[n]=1;
        smallpos[n-1] = 1;
        if( small[n-1] < a[n] ) smallpos[n-1]=2;

        for( int i=n-1;i>=1;i-- ){
            if( a[i] > tail[1] ) tail[1]=a[i];
            else if( a[i] < tail[len-1] )tail[len++]=a[i];
            else{
                    /// i ovdje mora upper ipak
      ///          int idx = lower_bound( tail,tail+len,a[i] )-tail;
      /// MOZDA PROBLEM **************************************************************
        int idx = uupper_bound( 1,len-1, a[i] );
    //    if( idx > 0 && tail[idx-1] == a[i]  ) idx--;
                idx++; /// dodamo, jer je ovaj iznad idx nemodifikovani, jos kad mu dodamo a[i] bice jos veci len
                tail[idx]=a[i];
            }
            if( i==0 ) break;
            if( small[i-1] > tail[1] ) smallpos[i-1] = 1;
            else if( small[i-1] < tail[len-1] ) smallpos[i-1]=len;
            else{
                  //  if( i==5 ) cout << " kako " << tail[1] <<  " " <<tail[2] << " " << tail[3] << " " << uupper_bound( 1,len-1,small[i-1] ) <<endl;
       //     smallpos[i-1]=upper_bound( tail+1,tail+len,small[i-1],cmp )-tail; /// treba li -tail?
            smallpos[i-1]=uupper_bound( 1,len-1,small[i-1] ); /// treba li -tail?
            smallpos[i-1]++;   /// dodamo 1 iz istog razloga ko gore
            }
        }
        /// sad kad imamo smallpos i bigpos, mozemo za small i big isto ici redom po tailove

        for( int i=0;i<len;i++ ) tail[i]=0;
        tail[1]=small[1];
        len=2;
     ///   sol=max( sol, smallpos[1] ) ; /// mislim da more i ovo
     /// trebam skontati kako idu rjesenja kad se sve poveca/smanji
        for( int i=2;i<=n;i++ ){
            if( small[i] < tail[1] ) tail[1]=small[i];
            else if( small[i] > tail[len-1] ) tail[len++]=small[i];
            else{
                int idx = lower_bound( tail+1,tail+len, small[i] ) - tail;
                tail[idx]=small[i];  /// treba li ++
            }
            sol = max( sol, len-1 + smallpos[i] - 1 ) ; /// -1 zbog njega samog. len je duzina lijevo, smallpos je desno koliko moze ici. prvo -1 jer len ide unaprijed
        }
   ///     sol=max( sol,len ); /// kad sve smanjis, mada je to isto ko kad ih sve ostavis
      ///  sol=max( sol, bigpos[n] );
      for( int i=0;i<len;i++ ) tail[len]=0;
      len=2;
      tail[1] = big[1];
      for( int i=n-1;i>=1;i-- ){
        if( big[i] > tail[1] ) tail[1]=big[i];
        else if( big[i] < tail[len-1] ) tail[len++] = big[i];
        else{
         //   int idx = upper_bound( tail+1, tail+len, big[i],cmp )-tail;
          int idx = uupper_bound( 1,len-1, big[i] );
            idx++;///  poveca se slicno ko iznad
        }
        sol=max( sol, len-1 + bigpos[i] - 1 );
      }
        /// jos mi fali da skontam kad sve treba povecat ili smanji, to cu valjda skontat
        cout << sol<<endl;


   /*     for( int i=1;i<=n;i++ ){
            cout << i << " "<< smallpos[i] << " " << bigpos[i] <<endl;
        }*/

      return 0;
    }

• Subtask 1: 0 / 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