ProgMe

Сортировка событий

Nov 2nd, 2023
766
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main() {
  6.     int n;
  7.     cin >> n;
  8.     pair<int, int> a[n];
  9.     for (auto &i : a) {
  10.         cin >> i.first >> i.second;
  11.     }
  12.  
  13.     int m;
  14.     cin >> m;
  15.     int points[m];
  16.     for (auto &i : points) {
  17.         cin >> i;
  18.     }
  19.  
  20.     vector<pair<int, int>> queries;
  21.     for (auto [l, r] : a) {
  22.         queries.emplace_back(l, -1);
  23.         queries.emplace_back(r, 1);
  24.     }
  25.     for (auto i : points) {
  26.         queries.emplace_back(i, 0);
  27.     }
  28.     sort(queries.begin(), queries.end());
  29.  
  30.     int ans = 0;
  31.  
  32.     pair<int, int> mx_ans = {-1, -1};
  33.     for (auto [query, type] : queries) {
  34.         if (type == -1) {
  35.             ans++;
  36.         } else if (type == 0) {
  37.             if (mx_ans.second < ans) {
  38.                 mx_ans = {query, ans};
  39.             }
  40.         } else {
  41.             ans--;
  42.         }
  43.     }
  44.     cout << mx_ans.first;
  45. }
Advertisement
Add Comment
Please, Sign In to add comment