HackerEarth Shooting Range problem solution

In this HackerEarth Shooting Range problem solution, Three friends Snow Gnome, Small Boy and Xephy were having fun in the biggest park in Lalalandia, when suddenly they saw the shooting range with prizes! As always, Small Boy asked for the biggest prize, and Snow Gnome said he would get it.

The shooting range consists of N towers each denoted by K lines (1 <= i <= N). Towers are described by blocks from the bottom to the top. Each block consists of Aij cubes and the shooter gets Bij coins for taking one cube in this block for 1 <= j <= Ki (see the picture for more explanation).

The shooter gets Q shots. He shoots the bullets in straight line on height Cl. After the bullet shoots the cube, it gets destroyed, and all cubes above it move down. Note that bullet, even after penetrating one tower, continues to go through and never goes down.

Xephy now wants to know how many points for each shot Snow Gnome got. Can you help him with that?

HackerEarth Shooting Range problem solution.

#include <bits/stdc++.h>

#define pb push_back
#define pp pop_back
#define mp make_pair
#define ld long double
#define f first
#define s second
#define ll long long

using namespace std;

const int N = 1e5 + 5;

const int mod = 1e9 + 7;

int n, q, k[N], a[10][N], b[10][N], sz = 1;

ll ans[N], add[N];

vector < pair < int, int > > lazy;

struct tree
{
  int l, r, s;
} T[N * 50];

void Add(int l, int r, int x)
{
  if (l > r) return;
  int L = lower_bound(lazy.begin(), lazy.end(), mp(l, -1)) - lazy.begin();
  int R = lower_bound(lazy.begin(), lazy.end(), mp(r + 1, -1)) - lazy.begin() - 1;
  add[L] += x;
  add[R + 1] -= x;
}

void upd(int x, int v = 1, int tl = 1, int tr = 1e9)
{
  if (tl == tr)
  {
    T[v].s++;
    return;
  }
  int tm = (tl + tr) / 2;
  if (x <= tm)
  {
    if (!T[v].l) T[v].l = ++sz;
    upd(x, T[v].l, tl, tm);
  }
  else
  {
    if (!T[v].r) T[v].r = ++sz;
    upd(x, T[v].r, tm + 1, tr);
  }
  T[v].s = 0;
  if (T[v].l) T[v].s += T[T[v].l].s;
  if (T[v].r) T[v].s += T[T[v].r].s;
}

int get(int x, int v = 1, int tl = 1, int tr = 1e9)
{
  if (tl == tr) return tl;
  int tm = (tl + tr) / 2;
  int now = tm - tl + 1 - T[T[v].l].s;
  if (now >= x) return get(x, T[v].l, tl, tm);
  else return get(x - now, T[v].r, tm + 1, tr);
}

int main()
{
  //ios_base::sync_with_stdio(0);
  #ifdef wws
    freopen("in", "r", stdin);
  #endif
  scanf("%d", &n);
  for (int i = 1;i <= n;i++)
  {
    scanf("%d", &k[i]);
    for (int j = 0;j < k[i];j++) scanf("%d%d", &a[j][i], &b[j][i]);
  }
  scanf("%d", &q);
  for (int i = 1;i <= q;i++)
  {
    int x; scanf("%d", &x);
    if (1e9 - T[1].s < x) continue;
    x = get(x);
    upd(x);
    lazy.pb(mp(x, i));
  }
  sort(lazy.begin(), lazy.end());
  for (int i = 1;i <= n;i++)
  {
    int cur = 0;
    for (int j = 0;j < k[i];j++)
    {
      Add(cur + 1, cur + a[j][i], b[j][i]);
      cur += a[j][i];
    }
  }
  for (int i = 0;i < lazy.size();i++)
  {
    if (i) add[i] += add[i - 1];
    ans[lazy[i].s] = add[i];
  }
  for (int i = 1;i <= q;i++) printf("%I64d\n", ans[i]);
  return 0;
}