Submission #76633143

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 1e6 + 5;
vector<int> a[N], b[N];
int s[N], t[N];

int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, d;
    cin >> n >> d;
    for(int i = 0; i < n; i++)
    {
        cin >> s[i] >> t[i];
        a[s[i]].push_back(i);
        b[t[i]].push_back(i);
    }
    set<int> st;
    ll ans = 0;
    for(int i = 1; i + d < N; i++)
    {
        for(int j : a[i])
        {
            if(t[j] >= i + d)
                st.insert(j);
        }
        ll sz = st.size();
        ans += sz * (sz - 1) / 2;
        for(int j : b[i + d])
            st.erase(j);
    }
    cout << ans << '\n';
    return 0;
}

Submission Info

Judge Result