Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
3.2 kB
3
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
long num;


long cal(vector<long > &leaders){
    vector<long> tail1(num, 0),tail2(num, 0),tail3(num, 0),tail4(num, 0);
    vector<long> defront(num,0),inback(num,0),infront(num,0),deback(num,0);
	long ct1=1;
	//////////////////////////////////////////////////////////decreasing
	tail1[0] = 0;
	defront[0]= leaders[0];
	for (int i = 1 ; i <= num-1 ; i++) {
		if (leaders[i] > defront[0]){
            defront[0] = leaders[i];
			tail1[i] = 0;
		}
		else if (leaders[i] < defront[ct1 - 1]){
            defront[ct1++] = leaders[i];
			tail1[i] = ct1 - 1;
		}
		else{
            defront[*lower_bound(defront.begin(), defront.begin() + num, leaders[i] , greater<long>())] = leaders[i];
            tail1[i] = *lower_bound(defront.begin(), defront.begin() + num, leaders[i] , greater<long>());
		}
	}

	ct1 = 1 ;
	inback[0] = leaders[num-1];
	tail2[0] = 0;
	for (int i = num-2; i >= 0 ; i--) {
		if (leaders[i] > inback[0]){
            inback[0] = leaders[i];
			tail2[i] = 0;
		}
		else if (leaders[i] < inback[ct1 - 1]){
            inback[ct1++] = leaders[i];
			tail2[i] = ct1 - 1;
		}
		else{
            inback[*lower_bound(inback.begin(), inback.begin() + num, leaders[i] , greater<long>())] = leaders[i];
            tail2[i] = *lower_bound(inback.begin(), inback.begin() + num, leaders[i] , greater<long>());
		}
	}

	long res1 = 0;
	for (int i = 0; i <= num - 1; i++){
        if (res1 < (tail1[i] + tail2[num-i-1] - 1)){
            res1 = (tail1[i] + tail2[num-i-1] - 1);
        }
	}
	/////////////////////////////////////////////////////////////increasing
	long ct2=1;
	tail3[0] = 0;
	infront[0]= leaders[0];
	for (int i = 1 ; i <= num-1 ; i++) {
		if (leaders[i] < infront[0]){
            infront[0] = leaders[i];
			tail3[i] = 0;
		}
		else if (leaders[i] > infront[ct2 - 1]){
            infront[ct2++] = leaders[i];
			tail3[i] = ct2 - 1;
		}
		else{
            infront[*lower_bound(infront.begin(), infront.begin() + num, leaders[i])] = leaders[i];
            tail3[i] = *lower_bound(infront.begin(), infront.begin() + num, leaders[i]);
		}
	}

	ct2 = 1 ;
	deback[0] = leaders[num-1];
	tail4[0] = 0;
	for (int i = num-2; i >= 0 ; i--) {
		if (leaders[i] < deback[0]){
            deback[0] = leaders[i];
			tail4[i] = 0;
		}
		else if (leaders[i] > deback[ct2 - 1]){
            deback[ct2++] = leaders[i];
			tail4[i] = ct2 - 1;
		}
		else{
            deback[*lower_bound(deback.begin(), deback.begin() + num, leaders[i] , greater<long>())] = leaders[i];
            tail4[i] = *lower_bound(deback.begin(), deback.begin() + num, leaders[i] , greater<long>());
		}
	}

	long res2 = 0;
	for (int i = 0; i <= num - 1; i++){
        if (res2 < (tail3[i] + tail4[num-i-1] - 1)){
            res2 = (tail3[i] + tail4[num-i-1] - 1);
        }
	}
	//return res1;
	return res2;
	//return max(res1,res2);
}

int main(){
	cin.tie(0);
    cin.sync_with_stdio(0);
    vector<long > leaders;
    cin>>num;

    for(int i = 0 ; i < num ; i ++){
        long a;
        cin>>a;
        leaders.push_back(a);
    }
    cout<<cal(leaders);
	return 0;
}