fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fastIO ios_base::sync_with_stdio(0); cin.tie(0);
  4. #define ll long long
  5. #define pb push_back
  6. #define all(x) x.begin(), x.end()
  7.  
  8. const int INF = 1e9;
  9. const int N = 1e5+5;
  10.  
  11. int n, a[N], dp[N], L[N], R[N], ans;
  12.  
  13. void update(int pos, int k){
  14.     for (int i=pos; i<=n; i+=i&-i){
  15.         dp[i] = max(dp[i], k);
  16.     }
  17. }
  18.  
  19. int get(int pos){
  20.     int ans = -INF;
  21.     for (int i=pos; i>0; i-=i&-i){
  22.         ans = max(ans, dp[i]);
  23.     }
  24.     return ans;
  25. }
  26.  
  27. void compress(){
  28.     map<int, int> mp;
  29.     int mpcnt = 0;
  30.     for (int i=1; i<=n; i++){
  31.         mp[a[i]] = 1;
  32.     }
  33.     for (auto& p: mp){
  34.         p.second = ++mpcnt;
  35.     }
  36.     for (int i=1; i<=n; i++){
  37.         a[i] = mp[a[i]];
  38.     }
  39. }
  40.  
  41. int main(){
  42.     fastIO;
  43.     cin >> n;
  44.     for (int i=1; i<=n; i++) cin >> a[i];
  45.     compress();
  46.     for (int i=1; i<=n; i++) dp[i] = -INF;
  47.     for (int i=1; i<=n; i++){
  48.         L[i] = max(1, get(a[i]-1)+1);
  49.         update(a[i], 1);
  50.         update(a[i], get(a[i]-1)+1);
  51.     }
  52.     for (int i=1; i<=n; i++) dp[i] = -INF;
  53.     for (int i=n; i>0; i--){
  54.         R[i] = max(1, get(a[i]-1)+1);
  55.         update(a[i], 1);
  56.         update(a[i], get(a[i]-1)+1);
  57.     }
  58.     for (int i=1; i<=n; i++){
  59.         ans = max(ans, min(R[i], L[i])*2-1);
  60.     }
  61.     cout << ans;
  62. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2MidWT
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!