Submission #75972298

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;

ll n,d;
ll ans;
ll dist;

ll qsum[200005];
int max_pos;

struct booth{
    ll x;
    ll s;
    int id;
}A[200005];


bool compare_booth(const booth &a, const booth &b){
   return a.x < b.x;
}

ll get_sum(int ss, int ee){
    return qsum[ee]-qsum[ss-1];
}

int search(int ll, int rr, int val){
    int res = -1, mid;
    if(ll > rr){return -1;}
    while(ll<=rr){
        mid = (ll+rr)/2;
        if(A[mid].x <= val){
            res = mid;
            ll = mid + 1;
        }
        else{
            rr = mid-1;
        }
    }
    return res;
}

/*
ll abs(ll a){
    if(a>0){return a;}
    return -a;
}
*/

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> d;
    for(int i=1;i<=n;i++){
        cin >> A[i].x >> A[i].s;
        A[i].id = i;
    }

    sort(A+1, A+n+1, compare_booth);

    for(int i=1; i<=n; i++){
        qsum[i] = qsum[i-1] + A[i].s;
    }

    for(int i = 1; i <= n; i++)
    {
        max_pos = search(i+1, n, A[i].x+d);
            //cout << "search " << i+1 << " " << n << " " << A[i].x+d << "\n";
        if(max_pos != (-1)){
            ans = ans + (A[i].s*get_sum(i+1, max_pos));
            //cout << i << " " << max_pos << " " << ans << "\n";
        }

    }


    cout << ans << "\n";
    return 0;
}

Submission Info

Judge Result