Untitled
unknown
plain_text
3 years ago
3.2 kB
4
Indexable
#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; }
Editor is loading...