N points, dist btw two points is defined as min(abs(x1-x2), abs(y1-y2)).find kth min dist.

Правка en1, от 7KIRA1999, 2023-05-07 09:20:13

I am trying to solve the given problem from here :

https://stackoverflow.com/questions/69444907/given-an-array-of-n-points-the-distance-between-two-points-is-defined-as-minab

using very similar problem : https://www.spoj.com/problems/NKPAIRS/en/

The code for this spoj problem looks something like this -

int n, m=50000, x[100005], y[100005];
long long ans;
struct segtree {
    int v[2*L];
    void upd (int P, int V) {
        P += L;
        while(P) {
            v[P] += V;
            P /= 2;
        }
    }
    int get (int S, int E) {
        S += L;
        E += L;
        int R = 0;
        while(S <= E) {
            if(S % 2 == 1) R += v[S++];
            if(E % 2 == 0) R += v[E--];
            S /= 2;
            E /= 2;
        }
        return R;
    }
} seg;
 
vector<int> b[150005];
 
long long solve2 (int d) {
    for(int i=1;i<=n;i++) {
        b[x[i]+y[i]-1].push_back(x[i]-y[i]+m);
    }
    for(int i=1;i<=2*m;i++) {
        for(auto &T : b[i]) {
            ans += seg.get(max(0,T-d), min(2*m,T+d));
            seg.upd(T, 1);
        }
        if(i - d <= 0) continue;
        for(auto &T : b[i-d]) {
            seg.upd(T, -1);
        }
    }
    return ans;
}

What changes should be done in this part so that the distance factor is updated in regards to my problem ?

Any help is appreciated.

Теги segment tree, binary search, hard problem

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский 7KIRA1999 2023-05-07 09:20:13 1502 Initial revision (published)