Advertisement
Guest User

B

a guest
Feb 18th, 2020
2,790
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.92 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. int OPEN = 0;
  6. int SHUT = 1;
  7. int LEFT = 2;
  8. int INSIDE = 3;
  9. int RIGHT = 4;
  10. int n, t;
  11.  
  12. struct comp {
  13.     bool operator()(vector<int> const &a, vector<int> const &b) const {
  14.         return a[0] < b[0];
  15.     }
  16. };
  17.  
  18. vector<vector<int> > kek;
  19. vector<pair<int, int> > status;
  20.  
  21. string match(int i) {
  22.     if (i == 2) return "LEFT";
  23.     if (i == 3) return "INSIDE";
  24.     else return "RIGHT";
  25. }
  26.  
  27. void show() {
  28.     for (int i = 0; i < n; i++) {
  29.         cout << i << ' ' << match(status[i].first) << ' ' << match(status[i].second) << endl;
  30.     }
  31. }
  32.  
  33. signed main() {
  34.     cin >> n >> t;
  35.     for (int i = 0; i < n; i++) {
  36.         int l, r;
  37.         cin >> l >> r;
  38.         vector<int> a(3);
  39.         a[0] = l;
  40.         a[1] = OPEN;
  41.         a[2] = i;
  42.         vector<int> b(3);
  43.         b[0] = r;
  44.         b[1] = SHUT;
  45.         b[2] = i;
  46.         kek.push_back(a);
  47.         kek.push_back(b);
  48.     }
  49.     sort(kek.begin(), kek.end(), comp());
  50.     status.resize(n, {RIGHT, RIGHT});
  51.     int rep = 0;
  52.     for (int l = 0, r = -1; l < kek.size(); l++) {
  53.         int x = kek[l][0];
  54.         while (r < kek.size() - 1 && kek[r + 1][0] - kek[l][0] < t) {
  55.             r++;
  56.             if (kek[r][1] == OPEN) {
  57.                 status[kek[r][2]].first = INSIDE;
  58.             } else {
  59.                 status[kek[r][2]].second = INSIDE;
  60.             }
  61.         }
  62.         int now = 0;
  63.         for (int i = 0; i < n; i++) {
  64.             if (status[i].first == INSIDE && status[i].second == INSIDE) {
  65.                 now++;
  66.             } else if (status[i].first == LEFT && status[i].second == RIGHT) {
  67.                 now--;
  68.             }
  69.         }
  70.         rep = max(rep, now);
  71.         if (kek[l][1] == OPEN) {
  72.             status[kek[l][2]].first = LEFT;
  73.         } else {
  74.             status[kek[l][2]].second = LEFT;
  75.         }
  76.     }
  77.     cout << rep << endl;
  78.     return 0;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement