Advertisement
YEZAELP

TOI13: Orchid

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