fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define endl '\n'
  6. #define sp ' '
  7. #define st first
  8. #define nd second
  9.  
  10. int a[30001];
  11. int res[30001];
  12.  
  13. int binary(int lo , int hi,int val){
  14.     int mid = (lo + hi) / 2;
  15.     while (mid != lo && hi != mid){
  16.         if (res[mid] >= val) hi = mid;
  17.             else lo = mid;
  18.         mid = (lo + hi)/2;
  19.     }
  20.     for (int i=lo ;i <= hi ;++i) if (res[i] >= val) return i;
  21.     return -1;
  22. }
  23.  
  24. int main(){
  25.     ios_base::sync_with_stdio(0);
  26.     //freopen ("f.txt","r" , stdin);
  27.     int n;  cin >> n;
  28.     for (int i=1;i<=n;++i) cin >> a[i];
  29.     int mxh = 0;
  30.     for (int i=1;i<=n;++i){
  31.         int x = binary(1 , mxh , a[i]);
  32.         if (x == -1) res[++mxh] = a[i];
  33.         else res[x] = min (res[x] , a[i]);
  34.     }
  35.     cout << mxh;
  36. }
  37.  
Runtime error #stdin #stdout 3.14s 3640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/K5dfcM
language:
C++14 (gcc 8.3)
created:
9 years 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!