Advertisement
DobriyKrot

Untitled

Sep 30th, 2023
783
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.49 KB | None | 0 0
  1. #include <algorithm>
  2. #include <array>
  3. #include <bitset>
  4. #include <cassert>
  5. #include <cctype>
  6. #include <cmath>
  7. #include <deque>
  8. #include <ext/pb_ds/assoc_container.hpp>
  9. #include <fstream>
  10. #include <iomanip>
  11. #include <iostream>
  12. #include <numeric>
  13. #include <map>
  14. #include <queue>
  15. #include <set>
  16. #include <sstream>
  17. #include <string>
  18. #include <unordered_map>
  19. #include <unordered_set>
  20. #include <vector>
  21.  
  22. using namespace std;
  23. using namespace __gnu_pbds;
  24.  
  25. #pragma GCC optimize("Ofast")
  26. #pragma GCC optimize("no-stack-protector")
  27. #pragma GCC optimize("unroll-loops")
  28. #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
  29. #pragma GCC optimize("fast-math")
  30.  
  31. template < typename firstType, typename secondType = null_type, class compare = less < firstType > >
  32. struct sett {
  33.     typedef tree <
  34.     firstType,
  35.     secondType,
  36.     compare,
  37.     rb_tree_tag,
  38.     tree_order_statistics_node_update
  39.     > _ ;
  40. };
  41.  
  42. #define int long long
  43. #define eb emplace_back
  44. #define pb push_back
  45. #define ld long double
  46. #define f first
  47. #define s second
  48. #define fast() { \
  49.     ios_base::sync_with_stdio(0); \
  50.     cin.tie(0); \
  51.     cout << fixed << setprecision(3); \
  52.     cerr << fixed << setprecision(11); \
  53. }
  54.  
  55. const int INF = 1e18 + 7;
  56. const ld EPS = 1e-7;
  57. const ld PI = 3.14159265358979323;
  58. const int MOD = 1e9 + 7;
  59. const int MAXN = 1001;
  60.  
  61.  
  62. signed main() {
  63.     fast();
  64.     int t;
  65.     cin >> t;
  66.     while (t--) {
  67.         int n;
  68.         cin >> n;
  69.         int a[n];
  70.         for (int i = 0; i < n; ++i) {
  71.             cin >> a[i];
  72.         }
  73.         int l = -1, r = n;
  74.         while (l + 1 < r) {
  75.             int m = (l + r) / 2;
  76.             int b[n];
  77.             for (int i = 0; i < n; ++i) {
  78.                 b[i] = a[i];
  79.             }
  80.             set<int> s;
  81.             for (int i = 0; i < m; ++i) {
  82.                 s.insert(b[i]);
  83.                 b[i] = 0;
  84.             }
  85.             for (int i = m; i < n; ++i) {
  86.                 if (s.contains(b[i])) {
  87.                     b[i] = 0;
  88.                 }
  89.             }
  90.             bool flag = true;
  91.             for (int i = m + 1; i < n; ++i) {
  92.                 if (b[i] < b[i - 1]) {
  93.                     flag = false;
  94.                 }
  95.             }
  96.             if (flag) {
  97.                 r = m;
  98.             } else {
  99.                 l = m;
  100.             }
  101.         }
  102.         set<int> s;
  103.         for (int i = 0; i < r; ++i) {
  104.             s.insert(a[i]);
  105.         }
  106.         cout << s.size() << '\n';
  107.     }
  108.     return 0;
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement