YEZAELP

PROG-1151: ต้นไม้ (Tree)

Jul 21st, 2020 (edited)
106
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.73 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int INF = 1e9;
  5. const int N = 2e5 + 10;
  6. int dp[N];
  7.  
  8. int main(){
  9.  
  10.     int n;
  11.     scanf("%d", &n);
  12.  
  13.     int sz = 0;
  14.  
  15.     for(int i=1;i<=n;i++){
  16.         int x;
  17.         scanf("%d", &x);
  18.         if(x > dp[sz]){
  19.             sz ++;
  20.             dp[sz] = x;
  21.         }
  22.         else {
  23.             int l = 1, r = sz, mid, mn = INF;
  24.             while(l <= r){
  25.                 int mid = (l + r) / 2;
  26.                 if(dp[mid] >= x){
  27.                     mn = min(mn, mid);
  28.                     r = mid - 1;
  29.                 }
  30.                 else
  31.                     l = mid + 1;
  32.             }
  33.             dp[mn] = x;
  34.         }
  35.     }
  36.  
  37.     printf("%d", sz);
  38.  
  39.     return 0;
  40. }
RAW Paste Data Copied