Tareq Intervals #1

#include <bits/stdc++.h>
#define F first
#define S second
//#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;
const int N = 2e5 + 9;
const int INF = 1e9 + 5;

int n, segTree[4 * N], k, res;
vector <pair <int, int> > intervals;
vector <int> tmp, compressed;

void updateTree (int v, int l, int r, int idx) {
    if (l == r) {
        segTree[v]++;

        return;
    }

    int mid = (l + r) / 2;
    if (idx <= mid)
        updateTree (2 * v, l, mid, idx);
    else updateTree (2 * v + 1, mid + 1, r, idx);

    segTree[v] = segTree[2 * v] + segTree[2 * v + 1];
    return;
}

int getQuery (int v, int l, int r, int L, int R) {
    if (L <= l && r <= R)
        return segTree[v];

    if (l > R || r < L)
        return 0;

    int mid = (l + r) / 2;
    int Q1 = getQuery (2 * v, l, mid, L, R);
    int Q2 = getQuery (2 * v + 1, mid + 1, r, L, R);

    return Q1 + Q2;
}

int getIdx (int x) {
    return lower_bound (compressed.begin(), compressed.end(), x) - compressed.begin() + 1;
}

void solve () {
    cin >> n >> k;

    vector <int> v;
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;

        if (l + k - 1 > r)
            continue;

        intervals.pb ({l, r});

        tmp.pb (l + k - 1);
        tmp.pb (r);
    }

    sort (tmp.begin(), tmp.end());
    for (int i = 0; i < (int) tmp.size(); i++) {
        if (i == 0) {
            compressed.pb (tmp[i]);

            continue;
        }

        if (tmp[i] != tmp[i - 1])
            compressed.pb (tmp[i]);
    }

    sort (intervals.begin(), intervals.end());
    for (auto p: intervals) {
        int L = p.F, R = p.S;

        updateTree (1, 1, n, getIdx(R));
        res = max (res, getQuery (1, 1, n, getIdx(L + k - 1), N - 1));
    }

    cout << res << "\n";

    return;
}

int main () {
    int t = 1;
    //cin >> t;

    while (t--)
        solve ();

    return 0;
}