Facebook
From amsen, 8 Months ago, written in C++.
Embed
Download Paste or View Raw
Hits: 59
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define greater greater123123
  5. #define less less123123
  6.  
  7. const int N = 3e5+100;
  8.  
  9. int a[N];
  10.  
  11. struct Seg{
  12.     int seg[4*N];
  13.  
  14.     Seg(){
  15.         memset(seg, 0, sizeof seg);
  16.     }
  17.  
  18.     int get(int l, int r, int s=0, int e=N, int id=1){
  19.         if(r<=s || e<=l)
  20.             return 0;
  21.         if(l<=s && e<=r)
  22.             return seg[id];
  23.         int mid = (s + e)/2;
  24.         return max(get(l, r, s, mid, 2*id), get(l, r, mid, e, 2*id+1));
  25.     }
  26.  
  27.     void upd(int x, int val, int s=0, int e=N, int id=1){
  28.         if(s>x || e<=x)
  29.             return;
  30.         if(e-s == 1){
  31.             seg[id] = max(seg[id], val);
  32.             return;
  33.         }
  34.         int mid = (s + e)/2;
  35.         upd(x, val, s, mid, 2*id);
  36.         upd(x, val, mid, e, 2*id+1);
  37.         seg[id] = max(seg[2*id], seg[2*id+1]);
  38.     }
  39. } greater, less;
  40.  
  41. int main(){
  42.         ios_base::sync_with_stdio(false);cin.tie(NULL);
  43.     int n;cin >> n;
  44.     for(int i=0 ; i<n ; i++)
  45.         cin >> a[i];
  46.     reverse(a, a+n);
  47.     int ans=0;
  48.     for(int i=0 ; i<n ; i++){
  49.         // <= a[i]
  50.         int cur1 = less.get(0, a[i]+1) + 1;
  51.         ans = max(ans, cur1);
  52.         // >= a[i]
  53.         int cur2 = greater.get(a[i], N) + 1;
  54.         greater.upd(a[i], cur1);
  55.         less.upd(a[i], cur2);
  56.     }
  57.  
  58.     cout << ans << "\n";
  59. }
  60.