SPSEQ - Sequences

Tác giả: hieult

Ngôn ngữ: C++

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
//#include <conio.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define DOWN(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a) REP(i,0,a);
#define pb  push_back
#define INF 1000000000
#define VI vector<int>
#define VVI vector<VI>
//ham
template <class T>  //so ko am
T gcd(T a, T b){if(b==0) return abs(a); else return gcd(b,a%b);}
template <class T>  
T lcm(T a, T b){ return a/gcd(a,b) *b;}

int n,a[100005],b[100005],l[100005],r[100005],m[100005],dis;
int main()
{
    //freopen("SPSEQ.IN", "rt", stdin);
    //freopen("SPSEQ.OUT", "wt", stdout);              
    scanf("%d",&n);
    REP(i,0,n-1)
    {
        scanf("%d",&a[i]);
        //cout<<a[i]<<" ";
        b[n-1-i]=a[i];
    }
   // cout<<endl;
    //Tinh left
    REP(i,0,n) m[i]=100005; //fill;
    dis=1;
    m[1]=a[0];
    l[0]=1;
    REP(i,1,n-1)
    {
        if(m[1]>=a[i]) {
            l[i]=1;
            m[1]=a[i];
            continue;
        }
        if(m[dis]<a[i])
        {
            l[i]=dis+1;
            m[dis+1]=a[i];
            dis++;
            continue;
        }
        
        int first=1,last=dis;
        while(last-1>first)
        {
            int mid=(first+last)/2;
            if(m[mid]<a[i])
                first=mid;
            else  //m[mid]>=a[i]
            {
                last=mid;    
            } 
        }
        l[i]=last;
        m[last]=a[i];
        
    }
    /*
    REP(i,0,n-1)
        cout<<i<<" "<<l[i]<<endl;
        */
    //return 0;
        //cout<<"Xong +_________________+"<<endl<<endl;
    //Tinh right
    REP(i,0,n) m[i]=100005; //fill;
    dis=1;
    m[1]=b[0];
    r[n-1]=1;
    REP(i,1,n-1)
    {
        if(m[1]>=b[i]) {
            r[n-1-i]=1;
            m[1]=b[i];
            continue;
        }
        if(m[dis]<b[i])
        {
            r[n-1-i]=dis+1;
            m[dis+1]=b[i];
            dis++;
            continue;
        }
        
        int first=1,last=dis;
        while(last-1>first)
        {
            int mid=(first+last)/2;
            if(m[mid]<b[i])
                first=mid;
            else  //m[mid]>=a[i]
            {
                last=mid;    
            } 
        }
        r[n-1-i]=last;
        m[last]=b[i];
        
    }
    /*
    REP(i,0,n-1)
        cout<<i<<" "<<r[i]<<endl;
        */
    int maxDis=-1;
    REP(i,0,n-1)
    {
        maxDis=max(maxDis,min(l[i],r[i]));    
    }
    
    if(maxDis==0) cout<<"0";
    else 
        cout<<2*maxDis-1;
}

Download