Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define f first
- #define s second
- using namespace std;
- typedef pair <int, int> pii;
- const int MAXN = 211111;
- const double eps = 0.5;
- vector <pii> a;
- vector <int> tree[4 * MAXN];
- void Merge(vector <int> & A, vector <int> & B, vector <int> & C){
- A.resize(B.size() + C.size());
- int i = 0, j = 0, ij = 0;
- while(i < B.size() && j < C.size()){
- if(B[i] < C[j])
- A[ij++] = B[i++];
- else
- A[ij++] = C[j++];
- }
- for(int k = i; k < B.size(); k++)
- A[ij++] = B[i];
- for(int k = j; k < C.size(); k++)
- A[ij++] = C[j];
- }
- void build(int tl, int tr, int v){
- if(tl == tr){
- tree[v].push_back(a[tl].s);
- return;
- }
- int mid = (tl + tr) >> 1;
- build(tl, mid, v << 1);
- build(mid + 1, tr, v << 1 | 1);
- Merge(tree[v], tree[v << 1], tree[v << 1 | 1]);
- }
- int query1(int tl, int tr, int v, int l, int r, double x){
- if(l > tr || r < tl)return 0;
- if(l <= tl && tr <= r){
- int cnt = lower_bound(tree[v].begin(), tree[v].end(), x) - tree[v].begin();
- return cnt;
- }
- int mid = (tl + tr) >> 1;
- return (query1(tl, mid, v << 1, l, r, x) + query1(mid + 1, tr, v << 1 | 1, l, r, x));
- }
- int query2(int tl, int tr, int v, int l, int r, double x){
- if(l > tr || r < tl)return 0;
- if(l <= tl && tr <= r){
- int cnt = upper_bound(tree[v].begin(), tree[v].end(), x) - tree[v].begin();
- return tree[v].size() - cnt;
- }
- int mid = (tl + tr) >> 1;
- return (query2(tl, mid, v << 1, l, r, x) + query2(mid + 1, tr, v << 1 | 1, l, r, x));
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- int n, t;
- cin >> n >> t;
- a.resize(n);
- vector <int> tmp(n);
- for(int i = 0; i < n; i++){
- int l, r;
- cin >> l >> r;
- a[i] = {l, r};
- tmp[i] = l;
- }
- sort(a.begin(), a.end());
- sort(tmp.begin(), tmp.end());
- build(0, n - 1, 1);
- int ans = 0;
- for(int i = 0; i < n; i++){
- double cur_l = a[i].f, cur_r = cur_l + t - eps;
- int pos = lower_bound(tmp.begin(), tmp.end(), cur_l) - tmp.begin();
- 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));
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement