HackerEarth Cluster Features problem solution

In this HackerEarth Cluster Features problem solution we have given n 2-dimensional data objects or points in a cluster, we can define the centroid (x0,y0) radius R and diameter D.

where R is the average distance from member objects to the centroid, and D is the average pairwise distance within the cluster. Both R and D reflect the tightness of the cluster around the centroid.

HackerEarth Cluster Features problem solution.

#include "bits/stdc++.h"

using namespace std;
struct ${$(){ios_base::sync_with_stdio(0);cin.tie(0);}}$;

const int N = 150000 + 5; // Change it
const int MX = 20000 + 5;

int x[N], y[N];
int x_left[N], x_right[N];
int y_down[N], y_up[N];

enum BorderState {
   OPEN,
   POINT,
   CLOSE,
};

struct segmentBorder {
   BorderState state;
   int y_d, y_u, x, id;
   bool operator <(const segmentBorder &s) {
      return x < s.x || (x == s.x && state < s.state);
   }
};


struct BIT {
   int n;
   long long LS, SS;
  
   BIT operator +(const BIT& a) const {
      return {n + a.n, LS + a.LS, SS + a.SS};
   }

   BIT operator -(const BIT& a) const {
      return {n - a.n, LS - a.LS, SS - a.SS};
   }
} B[MX];

BIT ans[2][N];

void update(int idx, int val) {
   long long val2 = val * 1LL * val;
   while(idx < MX) {
      B[idx].n += 1;
      B[idx].LS += val;
      B[idx].SS += val2;
      idx += idx & -idx;
   }
}

BIT get(int idx) {
   BIT ret = {0, 0LL, 0LL};
   while(idx > 0) {
      ret.n += B[idx].n;
      ret.LS += B[idx].LS;
      ret.SS += B[idx].SS;
      idx -= idx & -idx;
   } 
   return ret;
}

BIT get(int l, int r) {
   return get(r) - get(l - 1);
}

void go(int p, int q, int turn) {

   vector <segmentBorder> borders;
   for(int i = 0; i < p; i++) {
      borders.push_back({POINT, y[i], -1, x[i], -1});
   }

   for(int i = 0; i < q; i++) {
      segmentBorder left_border({OPEN, y_down[i], y_up[i], x_left[i], i});
      segmentBorder right_border({CLOSE, y_down[i], y_up[i], x_right[i], i});
      
      borders.push_back(left_border);
      borders.push_back(right_border);
   }

   sort(borders.begin(), borders.end());

   for(int i = 0; i < borders.size(); i++) {
      if(borders[i].state == POINT) {
         update(borders[i].y_d, borders[i].x);
      } else if(borders[i].state == OPEN) {
         BIT val = get(borders[i].y_d, borders[i].y_u);
         ans[turn][borders[i].id] = ans[turn][borders[i].id] - val;
      } else if(borders[i].state == CLOSE) {
         BIT val = get(borders[i].y_d, borders[i].y_u);
         ans[turn][borders[i].id] = ans[turn][borders[i].id] + val;
      } 
   }
}

long long magic(BIT t) {
   unsigned long long int ret = t.n * 1ULL * t.SS - t.LS * 1ULL * t.LS;
   ret = ret * 3ULL;
   ret += t.LS;
   return ret;
}

int main() {
   int p, q;
   scanf("%d %d", &p, &q);

   for(int i = 0; i < p; i++)
      scanf("%d %d", &x[i], &y[i]);

   for(int i = 0; i < q; i++)
      scanf("%d %d %d %d", &x_left[i], &x_right[i], &y_down[i], &y_up[i]);

   go(p, q, 0);

   for(int i = 0; i < p; i++) 
      swap(x[i], y[i]);

   for(int i = 0; i < q; i++) {
      swap(x_left[i], y_down[i]);
      swap(x_right[i], y_up[i]);
   }

   memset(B, 0, sizeof(B)); // NOT Required! WHY?

   go(p, q, 1);

   for(int i = 0; i < q; i++) {
      unsigned long long int val = magic(ans[0][i]) + magic(ans[1][i]);
      printf("%llu\n", val);
   }

   return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;

#define ll unsigned long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second

const int N = 1.5e5 + 10, logN = 15;
const int M = N * logN;
const int MAX = 20005;

struct data{
    int n;
    ll sumx2, sumy2, sumx, sumy;
    data(){n = sumx = sumy = sumx2 = sumy2 = 0;}
    data(int x, int y){n = 1, sumx = x, sumx2 = x * x, sumy = y, sumy2 = y * y;}
    data operator + (const data & D) const{
        data ret;
        ret.n = n + D.n;
        ret.sumx = sumx + D.sumx;
        ret.sumx2 = sumx2 + D.sumx2;
        ret.sumy = sumy + D.sumy;
        ret.sumy2 = sumy2 + D.sumy2;
        return ret;
    }
    data operator - (const data & D) const{
        data ret;
        ret.n = n - D.n;
        ret.sumx = sumx - D.sumx;
        ret.sumx2 = sumx2 - D.sumx2;
        ret.sumy = sumy - D.sumy;
        ret.sumy2 = sumy2 - D.sumy2;
        return ret;
    }
} tree[M];

int lft[M], rgt[M], cnt = 0;

data bit[MAX];
void update(int pos, const data & D){
    for(; pos < MAX; pos += (pos & (-pos))) bit[pos] = bit[pos] + D;
}

data get(int i){
    data ret;
    for(; i; i -= (i & -i)) ret = ret + bit[i];
    return ret;
}

data get(int l, int r){return get(r) - get(l - 1);}

void insert(int x, int y){
    data D = data(x, y);
    update(y, D);
}

ll get_ans(data D){
    return D.sumx + D.sumy + 3 * (D.n * (D.sumx2 + D.sumy2) -  D.sumx *  D.sumx -  D.sumy *  D.sumy);
}

map<pii, data> store[MAX];
vector<pii> queriesY[MAX];
vector<int> pointsY[MAX];

vector<pair<pii, pii>> queries;

data query(int x1, int y1, int x2, int y2){
    return store[x2][{y1, y2}] - store[x1 - 1][{y1, y2}];
}

void yes(int x, int y){assert(x >= 1 && x <= 20000 && y >= 1 && y <= 20000);}
int main(){
    int p, q;
    sd(p); sd(q);
    for(int i = 1; i <= p; i++){
        int x, y;
        sd(x); sd(y);
        yes(x, y);
        pointsY[x].push_back(y);
    }

    for(int i = 1; i <= q; i++){
        int a, b, c, d;
        sd(a); sd(c); sd(b); sd(d);
        yes(a, b); yes(c, d);
        queries.push_back({{a, b}, {c, d}});
        queriesY[a - 1].push_back({b, d});
        queriesY[c].push_back({b, d});
    }

    for(int x = 0; x < MAX; x++){
        for(int y : pointsY[x]) insert(x, y);
        for(auto y : queriesY[x]) store[x][y] = get(y.F, y.S);
    }

    for(auto it : queries){
        printf("%llu\n", get_ans(query(it.F.F, it.F.S, it.S.F, it.S.S)));
    }
}