rembocoder

Untitled

Apr 21st, 2023
736
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.67 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int int64_t
  6.  
  7. const int inf = 2e18;
  8. const int mod = 1e9 + 7;
  9.  
  10. bool cmp(const pair<int, pair<int, int>>& a,
  11.          const pair<int, pair<int, int>>& b) {
  12.     if (a.first != b.first) {
  13.         return a.first > b.first;
  14.     }
  15.     return a.second.first < b.second.first;
  16. }
  17.  
  18. bool is_loosely_dominated(int y, int z, set<pair<int, int>>& stairs) {
  19.     auto it = stairs.lower_bound(make_pair(y, -1));
  20.     return it != stairs.end() && it->second >= z;
  21. }
  22.  
  23. int32_t main() {
  24.     ios_base::sync_with_stdio(0);
  25.     cin.tie(0); cout.tie(0);
  26.     int n;
  27.     cin >> n;
  28.     vector<pair<int, pair<int, int>>> p(n);
  29.     for (int i = 0; i < n; i++) {
  30.         cin >> p[i].first;
  31.     }
  32.     for (int i = 0; i < n; i++) {
  33.         cin >> p[i].second.first;
  34.     }
  35.     for (int i = 0; i < n; i++) {
  36.         cin >> p[i].second.second;
  37.     }
  38.     sort(p.begin(), p.end(), cmp);
  39.     set<pair<int, int>> stairs;
  40.     int ans = 0;
  41.     for (int i = 0; i < n; i++) {
  42.         int y = p[i].second.first, z = p[i].second.second;
  43.         if (is_loosely_dominated(y + 1, z + 1, stairs)) {
  44.             ans++;
  45.             continue;
  46.         }
  47.         if (is_loosely_dominated(y, z, stairs)) {
  48.             continue;
  49.         }
  50.         vector<pair<int, int>> to_del;
  51.         auto it = stairs.lower_bound({y + 1, -1});
  52.         while (it != stairs.begin()) {
  53.             it--;
  54.             if (it->second > z) {
  55.                 break;
  56.             }
  57.             to_del.push_back(*it);
  58.         }
  59.         for (auto cur: to_del) {
  60.             stairs.erase(cur);
  61.         }
  62.         stairs.insert(make_pair(y, z));
  63.     }
  64.     cout << ans << '\n';
  65. }
  66.  
Advertisement
Add Comment
Please, Sign In to add comment