fork download 
  1.  
  2. /*
  3.     www.youtube.com/YugiHackerChannel
  4.     linktr.ee/YugiHacker
  5. */
  6. #include<bits/stdc++.h>
  7. #define el cout<<"\n"
  8. #define f0(i,n) for(int i=0;i<n;++i)
  9. #define f1(i,n) for(int i=1;i<=n;++i)
  10. #define maxn 200005
  11. using namespace std;
  12. int n, a[maxn], b[maxn], t[maxn * 4];
  13. void update(int id, int l, int r, int p, int v) {
  14.     if (l == r) {
  15.         t[id] = v;
  16.         return;
  17.     }
  18.     int mid = (l + r) / 2;
  19.     if (p <= mid) update(id*2, l, mid, p, v);
  20.     else update(id*2+1, mid+1, r, p, v);
  21.     t[id] = max(t[id*2], t[id*2+1]);
  22. }
  23. int get (int id, int l, int r, int u, int v) {
  24.     if (r < u || v < l) return 0;
  25.     if (u <= l && r <= v) return t[id];
  26.     int mid = (l + r) / 2;
  27.     return max(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
  28. }
  29. int main()
  30. {
  31.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  32.     cin >> n;
  33.     for (int i=1; i<=n; i++) {
  34.         cin >> a[i];
  35.         b[i] = a[i];
  36.     }
  37.     sort(b+1, b+n+1);
  38.     for (int i=1; i<=n; i++) {
  39.         int x = lower_bound(b+1, b+n+1, a[i]) - b;
  40.         int dp = get(1, 1, n, 1, x-1) + 1;
  41.         update(1, 1, n, x, dp);
  42.     }
  43.     cout << get(1, 1, n, 1, n);
  44. }
  45.  
Success #stdin #stdout 0.01s 5592KB
comments (?)
stdin 
5
1 2 3 5 4
stdout 
4
https://ideone.com/kJrxq2
language:
C++ (gcc 8.3)
created:
4 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!