Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. struct trip {
  9.     int t1, t2, s;
  10. };
  11.  
  12. bool comp(trip a, trip b) {
  13.     if (a.t1 < b.t1) {
  14.         return true;
  15.     }
  16.     else if (a.t1 > b.t1) {
  17.         return false;
  18.     }
  19.     else {
  20.         if (a.t2 < b.t2) {
  21.             return true;
  22.         }
  23.         else if (a.t2 > b.t2) {
  24.             return false;
  25.         }
  26.         else {
  27.             return a.s < b.s;
  28.         }
  29.     }
  30. }
  31.  
  32. int main() {
  33.     int t;
  34.     cin >> t;
  35.     int n;
  36.     cin >> n;
  37.     vector <trip> a(n);
  38.     for (int i = 0; i < n; i++) {
  39.         cin >> a[i].t1 >> a[i].t2;
  40.         a[i].t2 += t;
  41.         a[i].s = 1;
  42.     }
  43.     int m;
  44.     cin >> m;
  45.     a.resize(n + m);
  46.     for (int i = n; i < n + m; i++) {
  47.         cin >> a[i].t1 >> a[i].t2;
  48.         a[i].t2 += t;
  49.         a[i].s = 2;
  50.     }
  51.     sort(a.begin(), a.end(), comp);
  52.     int c1 = 0, c2 = 0;
  53.     int ans = 0;
  54.     priority_queue <int, vector <int>, greater<int>> q1, q2;
  55.     for (int i = 0; i < n + m; i++) {
  56.         if (a[i].s == 1) {
  57.             while (q1.size() > 0 && q1.top() <= a[i].t1) {
  58.                 q1.pop();
  59.                 c1++;
  60.             }
  61.             if (c1 == 0) {
  62.                 c1++;
  63.                 ans++;
  64.             }
  65.             c1--;
  66.             q2.push(a[i].t2);
  67.         }
  68.         else {
  69.             while (q2.size() > 0 && q2.top() <= a[i].t1) {
  70.                 q2.pop();
  71.                 c2++;
  72.             }
  73.             if (c2 == 0) {
  74.                 c2++;
  75.                 ans++;
  76.             }
  77.             c2--;
  78.             q1.push(a[i].t2);
  79.         }
  80.     }
  81.     cout << ans;
  82.     return 0;
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement