3772. JocCuLasere

#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

ifstream fin("lasere.in");
ofstream fout("lasere.out");

const int MAXN = 1e5 + 5;

struct award {
  int t, h;

  bool operator < (const award &A) const {
    return t < A.t;
  }
} e1[MAXN], e2[MAXN];

struct laser {
  int t, h1, h2, ind;

  bool operator < (const laser &A) const {
    return t < A.t;
  }
} l[MAXN];

int sol[MAXN], N, H[MAXN << 1], val, aib[MAXN << 1];
unordered_map<int,int> Hash;

void update(int x, int add) {
  for (int i = x; i <= val; i += i & -i)
    aib[i] += add;
}

int query(int l, int r) {
  int ans = 0;
  for (int i = r; i > 0; i -= i & -i)
    ans += aib[i];
  for (int i = l - 1; i > 0; i -= i & -i)
    ans -= aib[i];
  return ans;
}

void solve() {
  int Q;
  fin >> Q;
  int n = 0, m = 0;
  for (int i = 0; i < Q; ++i) {
    int type;
    fin >> type;
    if (type == 1) {
      int t, d, h;
      fin >> t >> d >> h;
      e1[++n] = {t, h};
      e2[n] = {t + d, h};
      H[++N] = h;
    } else {
      int t, h1, h2;
      fin >> t >> h1 >> h2;
      ++m;
      l[m] = {t, h1, h2, m};
      H[++N] = h1;
      H[++N] = h2;
    }
  }
  sort(H + 1, H + N + 1);
  for (int i = 1; i <= N; ++i) {
    if (H[i] == H[i - 1])
      continue;
    ++val;
    Hash[H[i]] = val;
  }
  for (int i = 1; i <= n; ++i)
    e1[i].h = e2[i].h = Hash[e1[i].h];
  for (int i = 1; i <= m; ++i) {
    l[i].h1 = Hash[l[i].h1];
    l[i].h2 = Hash[l[i].h2];
  }
  Hash.clear();
  sort(e1 + 1, e1 + n + 1);
  sort(e2 + 1, e2 + n + 1);
  sort(l + 1, l + m + 1);
  int p1 = 1, p2 = 1;
  int64 ans = 0;
  for (int i = 1; i <= m; ++i) {
    while (p1 <= n && e1[p1].t <= l[i].t) {
      update(e1[p1].h, 1);
      ++p1;
    }
    while (p2 <= n && e2[p2].t < l[i].t) {
      update(e2[p2].h, -1);
      ++p2;
    }
    sol[l[i].ind] = query(l[i].h1, l[i].h2);
    ans += sol[l[i].ind];
  }
  for (int i = 1; i <= m; ++i)
    fout << sol[i] << '\n';
  fout << ans << '\n';
}

void close_files() {
  fin.close();
  fout.close();
}

int main() {
  solve();
  close_files();
  return 0;
}