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