Untitled

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

long long num;

long long cal(vector<long long > &leaders){
    vector<long long> tail1(num, 0),tail2(num, 0),tail3(num, 0),tail4(num, 0);
	long long len1 = 1 ,len2 = 1 , len3 = 1 ,len4 = 1;
	//////////////////////////////////////////////////////////decreasing
	long long floor = 0;
	tail1[0] = leaders[0];
	for (int i = 1 ; i <= num-1 ; i++) {
        auto b1f = tail1.begin(), e1f = tail1.begin() + len1;
		auto it1 = lower_bound(b1f, e1f, leaders[i] , greater<long long>());
		if (leaders[i] > tail1[0]){
            tail1[0] = leaders[i];
		}
		else if (leaders[i] < tail1[len1 - 1]){
            tail1[len1++] = leaders[i];
            floor = i;
		}
		else{
            *it1 = leaders[i];
		}
	}

	tail3[0] = leaders[num-1];
	for (int i = num-2; i >= floor ; i--) {
        auto b1b = tail3.begin(), e1b = tail3.begin() + len2;
		auto it2 = lower_bound(b1b, e1b, leaders[i] , greater<long long>());
		if (leaders[i] > tail3[0]){
            tail3[0] = leaders[i];
		}
		else if (leaders[i] < tail3[len2 - 1]){
            tail3[len2++] = leaders[i];
		}
		else{
            *it2 = leaders[i];
		}
	}
	/////////////////////////////////////////////////////////////increasing
	long long peak = 0;
	tail2[0] = leaders[0];
	for (int i = 1 ; i <= num-1 ; i++) {
        auto b2f = tail2.begin(), e2f = tail2.begin() + len3;
		auto it3 = lower_bound(b2f, e2f, leaders[i]);
		if (leaders[i] < tail2[0]){
            tail2[0] = leaders[i];
		}
		else if (leaders[i] > tail2[len3 - 1]){
            tail2[len3++] = leaders[i];
            peak = i;
		}
		else{
            *it3 = leaders[i];
		}
	}

	tail4[0] = leaders[num-1];
	for (int i = num-2; i >= peak ; i--) {
        auto b2b = tail4.begin(), e2b = tail4.begin() + len4;
		auto it4 = lower_bound(b2b, e2b, leaders[i]);
		if (leaders[i] < tail4[0]){
            tail4[0] = leaders[i];
		}
		else if (leaders[i] > tail4[len4 - 1]){
            tail4[len4++] = leaders[i];
		}
		else{
            *it4 = leaders[i];
		}
	}
	//cout<<len1<<" "<<len2<<" "<<len3<<" "<<len4<<"\n";
	return max(len1+len2-1,len3+len4-1);
}

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

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