Fshl0

Tareq Intervals #1

Jan 15th, 2022
582
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. int n, segTree[4 * N], k, res;
  15. vector <pair <int, int> > intervals;
  16. vector <int> tmp, compressed;
  17.  
  18. void updateTree (int v, int l, int r, int idx) {
  19.     if (l == r) {
  20.         segTree[v]++;
  21.        
  22.         return;
  23.     }
  24.    
  25.     int mid = (l + r) / 2;
  26.     if (idx <= mid)
  27.         updateTree (2 * v, l, mid, idx);
  28.     else updateTree (2 * v + 1, mid + 1, r, idx);
  29.    
  30.     segTree[v] = segTree[2 * v] + segTree[2 * v + 1];
  31.     return;
  32. }
  33.  
  34. int getQuery (int v, int l, int r, int L, int R) {
  35.     if (L <= l && r <= R)
  36.         return segTree[v];
  37.    
  38.     if (l > R || r < L)
  39.         return 0;
  40.        
  41.     int mid = (l + r) / 2;
  42.     int Q1 = getQuery (2 * v, l, mid, L, R);
  43.     int Q2 = getQuery (2 * v + 1, mid + 1, r, L, R);
  44.  
  45.     return Q1 + Q2;
  46. }
  47.  
  48. int getIdx (int x) {
  49.     return lower_bound (compressed.begin(), compressed.end(), x) - compressed.begin() + 1;
  50. }
  51.  
  52. void solve () {
  53.     cin >> n >> k;
  54.    
  55.     vector <int> v;
  56.     for (int i = 1; i <= n; i++) {
  57.         int l, r;
  58.         cin >> l >> r;
  59.        
  60.         if (l + k - 1 > r)
  61.             continue;
  62.            
  63.         intervals.pb ({l, r});
  64.        
  65.         tmp.pb (l + k - 1);
  66.         tmp.pb (r);
  67.     }
  68.    
  69.     sort (tmp.begin(), tmp.end());
  70.     for (int i = 0; i < (int) tmp.size(); i++) {
  71.         if (i == 0) {
  72.             compressed.pb (tmp[i]);
  73.            
  74.             continue;
  75.         }
  76.        
  77.         if (tmp[i] != tmp[i - 1])
  78.             compressed.pb (tmp[i]);
  79.     }
  80.    
  81.     sort (intervals.begin(), intervals.end());
  82.     for (auto p: intervals) {
  83.         int L = p.F, R = p.S;
  84.        
  85.         updateTree (1, 1, n, getIdx(R));
  86.         res = max (res, getQuery (1, 1, n, getIdx(L + k - 1), N - 1));
  87.     }
  88.    
  89.     cout << res << "\n";
  90.    
  91.     return;
  92. }
  93.  
  94. int main () {
  95.     int t = 1;
  96.     //cin >> t;
  97.    
  98.     while (t--)
  99.         solve ();
  100.    
  101.     return 0;
  102. }
  103.  
RAW Paste Data