fork download
copy 
  1. /*
  2.     author  : [ Godsent ]
  3.     created : 2025.08.11 20:47:30
  4. */
  5.  
  6. #include <bits/stdc++.h>
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. #define el "\n"
  10. #define int long long
  11. #define lb lower_bound
  12. #define ub upper_bound
  13. #define fi first
  14. #define se second
  15. #define sz(x) ((int)(x).size())
  16. #define all(v) (v).begin(), (v).end()
  17. #define pb push_back
  18. #define prs(n) fixed << setprecision(n)
  19.  
  20. const int mod = 1e9 + 7;
  21. const int N = 2e5 + 5;
  22. const int INF = 1e18;
  23.  
  24. using namespace std;
  25. using namespace __gnu_pbds;
  26. template <typename T>
  27. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  28.  
  29. int n;
  30. int a[N];
  31.  
  32. signed main() {
  33.   ios_base::sync_with_stdio(false);
  34.   cin.tie(0);
  35.   cout.tie(0);
  36.  
  37. #ifndef ONLINE_JUDGE
  38.   freopen("test.in", "r", stdin);
  39.   freopen("test.out", "w", stdout);
  40. #endif
  41.  
  42.   cin >> n;
  43.   for (int i = 1; i <= n; i++)
  44.     cin >> a[i];
  45.  
  46.   multiset<int> s;
  47.   int res = 0;
  48.   for (int i = 1; i <= n; i++) {
  49.     auto it = ub(all(s), a[i]);
  50.     if (it == s.end()) {
  51.       s.insert(a[i]);
  52.       res++;
  53.       continue;
  54.     }
  55.     s.erase(it);
  56.     s.insert(a[i]);
  57.   }
  58.  
  59.   cout << res << el;
  60.  
  61.   return 0;
  62. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/FAgrMx
language:
C++14 (gcc 8.3)
created:
15 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!