Advertisement
Guest User

Untitled

a guest
Feb 28th, 2020
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.31 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <string>
  5. #include <vector>
  6. #include <unordered_set>
  7. #include <map>
  8. #include <unordered_map>
  9. #include <set>
  10. #include <numeric>
  11. #include <iomanip>
  12.  
  13. #define ll int64_t
  14. #define vll vector<int64_t>
  15. #define vd vector<double>
  16. #define ld long double
  17. #define forin(i, a, n) for (int64_t i = a; i < n; ++i)
  18. #define forn(i, n) for (int64_t i = 0; i < n; ++i)
  19. #define pb push_back
  20. #define eb emplace_back
  21.  
  22. using namespace std;
  23.  
  24. //void build(vector<int> &t, vector<pair<int, int>> &pallets, int v, int l, int r) {
  25. //    if (r - l == 1)
  26. //        t[v] = pallets[l].second;
  27. //    else {
  28. //        int m = (l + r) / 2;
  29. //        build(t, pallets, v * 2 + 1, l, m);
  30. //        build(t, pallets, v * 2 + 2, m, r);
  31. //        t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
  32. //    }
  33. //}
  34.  
  35. void build(vector<int> &t, vector<pair<int, int>> &pallets, int n) {
  36.     forn(i, n) {
  37.         t[n - 1 + i] = pallets[i].second;
  38.     }
  39.     for (int i = n - 2; i >= 0; --i) {
  40.         t[i] = max(t[i * 2 + 1], t[i * 2 + 2]);
  41.     }
  42. }
  43.  
  44. //int find_max(vector<int> &t, int v, int tl, int tr, int l, int r) {
  45. //    if (tl < l || tr > r)
  46. //        return INT32_MIN;
  47. //    if (l >= tl && r <= tr)
  48. //        return t[v];
  49. //    int tm = (tl + tr) / 2;
  50. //    return max(find_max(t, v * 2 + 1, tl, tm, l, min(r, tm)),
  51. //               find_max(t, v * 2 + 2, tm, tr, max(l, tm), r));
  52. //}
  53.  
  54. int find_max(vector<int> &t, int left, int right) {
  55.     int left_res = INT32_MIN;
  56.     int right_res = INT32_MIN;
  57.     while (left < right) {
  58.         if (left % 2 == 0) {
  59.             left_res = max(left_res, t[left]);
  60.         }
  61.         left /= 2;
  62.         if (right % 2 == 1) {
  63.             right_res = max(right_res, t[right]);
  64.         }
  65.         right /= 2;
  66.     }
  67.  
  68.     if (left == right) {
  69.         left_res = max(left_res, t[left]);
  70.     }
  71.  
  72.     return max(left_res, right_res);
  73. }
  74.  
  75. //int bin_search(vector<pair<int, int>> &pallets, int len) {
  76. //    int l = -1;
  77. //    int r = pallets.size();
  78. //    while (l < r - 1) {
  79. //        int m = (l + r) / 2;
  80. //        if (pallets[m].first < len) {
  81. //            l = m + 1;
  82. //        } else {
  83. //            r = m;
  84. //        }
  85. //    }
  86. //
  87. //    return r + 1;
  88. //}
  89.  
  90. int main() {
  91.     cin.tie(nullptr);
  92.     cout.tie(nullptr);
  93.     ios_base::sync_with_stdio(false);
  94.  
  95.     int n;
  96.     cin >> n;
  97.     vector<pair<int, int>> pallets;
  98.     forn(i, n) {
  99.         int a, b;
  100.         cin >> a >> b;
  101.         int _min = min(a, b);
  102.         int _max = max(a, b);
  103.         pallets.emplace_back(_min, _max);
  104.     }
  105.  
  106.     sort(pallets.begin(), pallets.end());
  107.     vector<int> lengths;
  108.     for (auto pallet : pallets) {
  109.         lengths.push_back(pallet.first);
  110.     }
  111.     int size = n * 4 - 1;
  112.     vector<int> t(size, INT32_MIN);
  113.     build(t, pallets, n);
  114. //    build(t, pallets, 0, 0, size);
  115.  
  116.     int good = 0;
  117.     forn(i, n) {
  118.         int len = pallets[i].first;
  119.         int width = pallets[i].second;
  120.  
  121.         auto iter = upper_bound(lengths.begin(), lengths.end(), len);
  122.         if (iter == lengths.end()) {
  123.             continue;
  124.         }
  125.         int v = iter - lengths.begin();
  126.         int max_width = find_max(t, size - n * 2 + v, size);
  127.         if (max_width > width) {
  128.             ++good;
  129.         }
  130.  
  131.     }
  132.  
  133.     cout << n - good;
  134.  
  135.     return 0;
  136. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement