Advertisement
Guest User

Untitled

a guest
Jan 19th, 2019
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.33 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define f first
  3. #define s second
  4.  
  5. using namespace std;
  6. typedef pair <int, int> pii;
  7.  
  8. const int MAXN = 211111;
  9. const double eps = 0.5;
  10. vector <pii> a;
  11. vector <int> tree[4 * MAXN];
  12.  
  13. void Merge(vector <int> & A, vector <int> & B, vector <int> & C){
  14.     A.resize(B.size() + C.size());
  15.     int i = 0, j = 0, ij = 0;
  16.     while(i < B.size() && j < C.size()){
  17.         if(B[i] < C[j])
  18.             A[ij++] = B[i++];
  19.         else
  20.             A[ij++] = C[j++];
  21.     }
  22.     for(int k = i; k < B.size(); k++)
  23.         A[ij++] = B[i];
  24.     for(int k = j; k < C.size(); k++)
  25.         A[ij++] = C[j];
  26. }
  27.  
  28. void build(int tl, int tr, int v){
  29.     if(tl == tr){
  30.         tree[v].push_back(a[tl].s);
  31.         return;
  32.     }
  33.     int mid = (tl + tr) >> 1;
  34.     build(tl, mid, v << 1);
  35.     build(mid + 1, tr, v << 1 | 1);
  36.     Merge(tree[v], tree[v << 1], tree[v << 1 | 1]);
  37. }
  38.  
  39. int query1(int tl, int tr, int v, int l, int r, double x){
  40.     if(l > tr || r < tl)return 0;
  41.     if(l <= tl && tr <= r){
  42.         int cnt = lower_bound(tree[v].begin(), tree[v].end(), x) - tree[v].begin();
  43.         return cnt;
  44.     }
  45.     int mid = (tl + tr) >> 1;
  46.     return (query1(tl, mid, v << 1, l, r, x) + query1(mid + 1, tr, v << 1 | 1, l, r, x));
  47. }
  48.  
  49. int query2(int tl, int tr, int v, int l, int r, double x){
  50.     if(l > tr || r < tl)return 0;
  51.     if(l <= tl && tr <= r){
  52.         int cnt = upper_bound(tree[v].begin(), tree[v].end(), x) - tree[v].begin();
  53.         return tree[v].size() - cnt;
  54.     }
  55.     int mid = (tl + tr) >> 1;
  56.     return (query2(tl, mid, v << 1, l, r, x) + query2(mid + 1, tr, v << 1 | 1, l, r, x));
  57. }
  58.  
  59. int main()
  60. {
  61.     ios_base::sync_with_stdio(0);
  62.     cin.tie(0);
  63.     int n, t;
  64.     cin >> n >> t;
  65.     a.resize(n);
  66.     vector <int> tmp(n);
  67.     for(int i = 0; i < n; i++){
  68.         int l, r;
  69.         cin >> l >> r;
  70.         a[i] = {l, r};
  71.         tmp[i] = l;
  72.     }
  73.     sort(a.begin(), a.end());
  74.     sort(tmp.begin(), tmp.end());
  75.     build(0, n - 1, 1);
  76.     int ans = 0;
  77.     for(int i = 0; i < n; i++){
  78.         double cur_l = a[i].f, cur_r = cur_l + t - eps;
  79.         int pos = lower_bound(tmp.begin(), tmp.end(), cur_l) - tmp.begin();
  80.         ans = max(ans, query1(0, n - 1, 1, i, n - 1, cur_l + t - eps) - (i != 0 ? query2(0, n - 1, 1, 0, pos - 1, cur_l + t - eps): 0));
  81.     }
  82.     cout << ans << '\n';
  83.     return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement