Transmitters problem for Algorithms Class 2018-2019

transmitters.cpp

// Transmitters-Receivers Problem for NTUA Algorithms 2018-2019 Class
// Author : Marios Papachristou
// Binary indexed tree implementation taken from
// https://medium.com/@harekrishnamahto18/range-sum-and-update-in-arrays-competitive-programming-82ae5039a16f

#include<bits/stdc++.h>
#define MAXN 1000000
using namespace std;
int b[MAXN];

struct transmitter {
  int T, R, index;
  bool is_transmitter = false;

  bool operator< (const transmitter &other) const {
    return T - R < other.T - other.R;
  }

  transmitter (int t, int r, int i) : T(t), R(r), index(i) {};

} ;

void update(int x,int val, int n) {
  b[x]+=(val);
  x+=(x&-x);
  while(x<=n)
  {
    b[x]+=(val);
    x+=(x&-x);
  }
}
int query(int i,int j, int n) {

  i=i-1;
  int sum1=b[i];
  i-=(i&-i);
  while(i>0)
  {

    sum1+=(b[i]);
    i-=(i&-i);
  }
  int sum2=b[j];
  j-=(j&-j);
  while(j>0)
  {
    sum2+=b[j];
    j-=(j&-j);
  }
  return(sum2-sum1);
}
int main()
{
  int n;
  cin>>n;

  for(int i = 1; i < n + 1; i++) update(i, 0, n);

  int t, r;

  vector<transmitter> A;

  for (int i = 1; i <= n; i++) {
    cin >> t >> r;
    A.push_back(transmitter(t, r, i));
  }

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

  int count = 0;
  int i = 0;

  while (count <= n / 2) {
    if (A[i].index != n && query(A[i].index + 1, n, n) <= n - 1 - A[i].index) {
      count++;
      A[i].is_transmitter = true;
      update(A[i].index, 1, n);
    }
    i++;
  }


  int total = 0;

  for (transmitter t : A)
    total += t.T * t.is_transmitter + (1 - t.is_transmitter) * t.R;

  printf("%d\n", total);

}