Fshl0

Tareq Intervals #2

Jan 15th, 2022
607
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. //#define mp make_pair
  5. #define pb push_back
  6.  
  7. using namespace std;
  8. typedef long long ll;
  9.  
  10. const int MOD = 1e9 + 7;
  11. const int N = 2e5 + 9;
  12. const int INF = 1e9 + 5;
  13.  
  14. vector <pair <int, int> > events;
  15.  
  16. bool cmp (pair <int, int> p1, pair <int, int> p2) {
  17.     if (p1.F == p2.F)
  18.         return p1.S > p2.S;
  19.     return p1.F <= p2.F;
  20. }
  21.  
  22. void solve () {
  23.     int n, k;
  24.     cin >> n >> k;
  25.    
  26.     for (int i = 1; i <= n; i++) {
  27.         int l, r;
  28.         cin >> l >> r;
  29.        
  30.         if (l + k - 1 > r)
  31.             continue;
  32.        
  33.         events.pb ({l, +1});
  34.         events.pb ({r - k + 1, -1});
  35.     }
  36.    
  37.     int res = 0, currentlyOpened = 0;
  38.     sort (events.begin(), events.end(), cmp);
  39.    
  40.     for (auto e: events) {
  41.         currentlyOpened += e.S;
  42.         res = max (res, currentlyOpened);
  43.     }
  44.    
  45.     cout << res << "\n";
  46.    
  47.     return;
  48. }
  49.  
  50. int main () {
  51.     int t = 1;
  52.     //cin >> t;
  53.    
  54.     while (t--)
  55.         solve ();
  56.    
  57.     return 0;
  58. }
  59.  
RAW Paste Data