fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define forinc(i, a, b) for(int i = a; i <= b; i++)
  6. #define maxn 229999
  7. int n, ans, a[maxn], bit[maxn], f[maxn];
  8. vector<int> b;
  9.  
  10. void update(int u, int x) {
  11.     for(; u <= n; u += (u & (-u)))
  12.         bit[u] = max(bit[u], x);
  13. }
  14.  
  15. int get(int u) {
  16.     int res = -1;
  17.     for(; u; u -= (u & (-u)))
  18.         res = max(res, bit[u]);
  19.     return res;
  20. }
  21.  
  22. signed main() {
  23.     cin >> n;
  24.     forinc(i, 1, n) {
  25.         cin >> a[i];
  26.         b.push_back(a[i]);
  27.     }
  28.  
  29.     sort(b.begin(), b.end());
  30.     forinc(i, 1, n) {
  31.         int pos = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 2;
  32.         f[i] = get(pos-1) + 1;
  33.         update(pos, f[i]);
  34.         ans = max(ans, f[i]);
  35.     }
  36.  
  37.     cout << ans;
  38. }
  39.  
Success #stdin #stdout 0.01s 5604KB
comments (?)
stdin
copy 
9
1 2 3 4 5 6 7 8 9
stdout
copy 
9
https://ideone.com/2by14O
language:
C++14 (gcc 8.3)
created:
1 year 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!