fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 1e6 + 5;
  5.  
  6. long long n;
  7. long long a[MaxN], b[MaxN];
  8. long long tree[4 * MaxN];
  9.  
  10. void input()
  11. {
  12.     cin >> n;
  13.     for (long long i = 1; i <= n; i++)
  14.         cin >> a[i];
  15. }
  16.  
  17. void update(long long id, long long l, long long r, long long pos, long long val)
  18. {
  19.     if (l == r)
  20.     {
  21.         tree[id] = max(tree[id], val);
  22.         return;
  23.     }
  24.  
  25.     long long mid = (l + r) / 2;
  26.  
  27.     if (pos <= mid)
  28.         update(id * 2, l, mid, pos, val);
  29.     else
  30.         update(id * 2 + 1, mid + 1, r, pos, val);
  31.  
  32.     tree[id] = max(tree[id * 2], tree[id * 2 + 1]);
  33. }
  34.  
  35. long long query(long long id, long long l, long long r, long long u, long long v)
  36. {
  37.     if (v < l || r < u)
  38.         return 0;
  39.  
  40.     if (u <= l && r <= v)
  41.         return tree[id];
  42.  
  43.     long long mid = (l + r) / 2;
  44.  
  45.     return max(query(id * 2, l, mid, u, v),
  46.                query(id * 2 + 1, mid + 1, r, u, v));
  47. }
  48.  
  49. void solve()
  50. {
  51.     for (long long i = 1; i <= n; i++)
  52.         b[i] = a[i];
  53.  
  54.     sort(b + 1, b + n + 1);
  55.  
  56.     long long sz = unique(b + 1, b + n + 1) - b - 1;
  57.  
  58.     long long ans = 1;
  59.  
  60.     for (long long i = 1; i <= n; i++)
  61.     {
  62.         long long pos = lower_bound(b + 1, b + sz + 1, a[i]) - b;
  63.  
  64.         long long cur;
  65.  
  66.         if (pos == 1)
  67.             cur = 1;
  68.         else
  69.             cur = query(1, 1, sz, 1, pos - 1) + 1;
  70.  
  71.         update(1, 1, sz, pos, cur);
  72.  
  73.         ans = max(ans, cur);
  74.     }
  75.  
  76.     cout << ans;
  77. }
  78.  
  79. int main()
  80. {
  81.     ios_base::sync_with_stdio(0);
  82.     cin.tie(0);
  83.  
  84.     input();
  85.     solve();
  86.  
  87.     return 0;
  88. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/9FpE3J
language:
C++14 (gcc 8.3)
created:
9 hours 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!