Submission #1173642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173642		avighna	Examination (JOI19_examination)	C++20	0 / 100	130 ms	56016 KiB

examination

#include <bits/stdc++.h>

struct Quadtree {
public:
  Quadtree *a, *b, *c, *d;
  int tl, tr, tu, td;
  int val = 0;

  Quadtree() {}
  Quadtree(int tl, int tr, int tu, int td)
      : tl(tl), tr(tr), tu(tu), td(td), a(nullptr), b(nullptr), c(nullptr),
        d(nullptr) {}

  void add(int x, int y, int del);
  int query(int x2, int y2);
};

Quadtree trees[int(1e6)];
int trees_idx = 0;

Quadtree *get_qt(int tl, int tr, int tu, int td) {
  trees[trees_idx].tl = tl;
  trees[trees_idx].tr = tr;
  trees[trees_idx].tu = tu;
  trees[trees_idx].td = td;
  return &trees[trees_idx++];
}

void Quadtree::add(int x, int y, int del) {
  int tm1 = (tl + tr) / 2;
  int tm2 = (tu + td) / 2;
  if (tl == tr and tu == td) {
    val += del;
    return;
  }
  if (x <= tm1 and y <= tm2) {
    a = a ? a : get_qt(tl, tm1, tu, tm2);
    a->add(x, y, del);
  } else if (x > tm1 and y <= tm2) {
    b = b ? b : get_qt(tm1 + 1, tr, tu, tm2);
    b->add(x, y, del);
  } else if (x <= tm1 and y > tm2) {
    c = c ? c : get_qt(tl, tm1, tm2 + 1, td);
    c->add(x, y, del);
  } else if (x > tm1 and y > tm2) {
    d = d ? d : get_qt(tm1 + 1, tr, tm2 + 1, td);
    d->add(x, y, del);
  }
  val =
      (a ? a->val : 0) + (b ? b->val : 0) + (c ? c->val : 0) + (d ? d->val : 0);
}

int Quadtree::query(int x2, int y2) {
  // x1 = 0, y1 = 0
  if (x2 < tl or y2 < tu) {
    return 0;
  }
  // [x1 [tl, tr] x2] and [y1 [tu, td] y2]
  if (tr <= x2 and td <= y2) {
    return val;
  }
  return (a ? a->query(x2, y2) : 0) + (b ? b->query(x2, y2) : 0) +
         (c ? c->query(x2, y2) : 0) + (d ? d->query(x2, y2) : 0);
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, q;
  std::cin >> n >> q;
  std::vector<std::pair<int, int>> a(n);
  Quadtree qt1(0, (1 << 17) - 1, 0, (1 << 17) - 1);
  //   Quadtree qt2(0, (1 << 22) - 1, 0, (1 << 22) - 1);
  auto update = [&](Quadtree &qt, int x, int y) {
    qt.add(0, 0, 1);
    qt.add(0, y + 1, -1);
    qt.add(x + 1, 0, -1);
    qt.add(x + 1, y + 1, 1);
  };
  for (auto &[s, t] : a) {
    std::cin >> s >> t;
    // all queries <= s and <= t are valid
    update(qt1, s, t);
    // other case
    // update(qt2, s + t, t);
  }
  for (int i = 0, x, y, z; i < q; ++i) {
    std::cin >> x >> y >> z;
    if (x + y >= z) {
      std::cout << qt1.query(x, y) << '\n';
    } else {
      //   std::cout << qt2.query(0, z, 0, y) << '\n';
    }
  }
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 20
• Subtask 3: 0 / 21
• Subtask 4: 0 / 57