fork download
copy 
  1. /**
  2.  *    author:  orzvanh14 ( Độc cô cầu đặc )
  3.  *    created: 20.05.2026 21:04:02
  4.  *    too lazy to update time
  5. **/
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. #define int long long
  11. #define nn "\n"
  12. #define pb push_back
  13. #define all(a) a.begin(), a.end()
  14.  
  15. const int N = 1e5 + 5;
  16.  
  17. int n, a[N];
  18.  
  19. void nhap(){
  20.     cin >> n;
  21.     for(int i = 1; i <= n; i++){
  22.         cin >> a[i];
  23.     }
  24. }
  25.  
  26. void solve(){
  27.     vector<int> lis;
  28.  
  29.     for(int i = 1; i <= n; i++){
  30.  
  31.         int pos = lower_bound(all(lis), a[i]) - lis.begin();
  32.  
  33.         if(pos == lis.size()){
  34.             lis.pb(a[i]);
  35.         }
  36.         else{
  37.             lis[pos] = a[i];
  38.         }
  39.     }
  40.  
  41.     cout << lis.size() << nn;
  42. }
  43.  
  44. signed main(){
  45.     ios_base::sync_with_stdio(0);
  46.     cin.tie(0);
  47.  
  48.     nhap();
  49.     solve();
  50.  
  51.     return 0;
  52. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5
2 1 4 3 5
stdout
copy 
3
https://ideone.com/Ncmx7n
language:
C++14 (gcc 8.3)
created:
5 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!