Submission #56550664

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int maxn = 4e6 + 10;
const int zero = 2e6 + 5;

long long dx[maxn], dy[maxn];

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

    int n, d;
    cin>>n>>d;

    vector<int> vx(n), vy(n);
    for(int i = 0; i < n; i++){
        cin>>vx[i]>>vy[i];
        vx[i] += zero;
        vy[i] += zero;
    }

    sort(vx.begin(), vx.end());
    sort(vy.begin(), vy.end());

    for(int i = 0; i < n; i++){
        dx[0] += vx[i];
        dy[0] += vy[i];
    }

    int add = -n;
    int j = 0;
    for(int i = 1; i < maxn; i++){
        dx[i] = dx[i-1] + add;
        while(j < n && vx[j] == i){
            add += 2;
            ++j;
        }
    }

    add = -n;
    j = 0;
    int pos = 0;
    for(int i = 1; i < maxn; i++){
        dy[i] = dy[i-1] + add;
        while(j < n && vy[j] == i){
            add += 2;
            ++j;
        }
        if(dy[i] < dy[pos]) pos = i;
    }

    long long ans = 0;
    for(int i = 0; i < maxn; i++){
        if(dx[i] + dy[pos] > d) continue;

        int rem = d - dx[i];

        {
            int lo = pos, hi = maxn;
            while(lo + 1 < hi){
                int mid = (lo + hi) / 2;
                if(dy[mid] <= rem) lo = mid;
                else hi = mid;
            }
            ans += lo - pos + 1;
        }
        {
            int lo = 0, hi = pos;
            while(lo + 1 < hi){
                int mid = (lo + hi) / 2;
                if(dy[mid] <= rem) hi = mid;
                else lo = mid;
            }
            ans += pos - hi;
        }
    }

    cout << ans << '\n';

    return 0;
}

Submission Info

Judge Result