#include <iostream>
#include <deque>
#include <vector>
using namespace std;
const int MAX_N = 1e6;
int n, a[MAX_N + 1], res;
pair<int,int> p[MAX_N + 2];
deque<int> dq;
vector<int> v;
void dq_insert(int x){
while(!dq.empty() && a[dq.back()] <= a[x]) dq.pop_back();
dq.push_back(x);
}
int dq_get_max(){
return a[dq.front()];
}
void vector_insert(int x){
if (v.empty() || a[x] > v.back()) v.push_back(a[x]);
}
int vector_get_larger_than_x_cnt(int x){
auto it = upper_bound(v.begin(), v.end(), x);
if (it == v.end()) return 0;
return distance(it, v.end());
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = n ; i>= 1; i--){
dq_insert(i);
p[i] = {dq.size(), dq_get_max()};
}
for(int i = 1; i<=n ; i++){
vector_insert(i);
int cnt = vector_get_larger_than_x_cnt(p[i+1].second);
res = max(res, cnt + p[i+1].first);
}
cout << res << endl;
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include <iostream> #include <deque> #include <vector> using namespace std; const int MAX_N = 1e6; int n, a[MAX_N + 1], res; pair<int,int> p[MAX_N + 2]; deque<int> dq; vector<int> v; void dq_insert(int x){ while(!dq.empty() && a[dq.back()] <= a[x]) dq.pop_back(); dq.push_back(x); } int dq_get_max(){ return a[dq.front()]; } void vector_insert(int x){ if (v.empty() || a[x] > v.back()) v.push_back(a[x]); } int vector_get_larger_than_x_cnt(int x){ auto it = upper_bound(v.begin(), v.end(), x); if (it == v.end()) return 0; return distance(it, v.end()); } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = n ; i>= 1; i--){ dq_insert(i); p[i] = {dq.size(), dq_get_max()}; } for(int i = 1; i<=n ; i++){ vector_insert(i); int cnt = vector_get_larger_than_x_cnt(p[i+1].second); res = max(res, cnt + p[i+1].first); } cout << res << endl; } |
English