Submission #1173619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173619		avighna	Examination (JOI19_examination)	C++20	0 / 100	3094 ms	158220 KiB

examination

#include <bits/stdc++.h>

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

  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) {}

  ~Quadtree() {
    delete a;
    delete b;
    delete c;
    delete d;
  }

  void 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 : new Quadtree(tl, tm1, tu, tm2);
      a->add(x, y, del);
    } else if (x > tm1 and y <= tm2) {
      b = b ? b : new Quadtree(tm1 + 1, tr, tu, tm2);
      b->add(x, y, del);
    } else if (x <= tm1 and y > tm2) {
      c = c ? c : new Quadtree(tl, tm1, tm2 + 1, td);
      c->add(x, y, del);
    } else if (x > tm1 and y > tm2) {
      d = d ? d : new Quadtree(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 query(int x1, int x2, int y1, int y2) {
    // [tl, tr] [x1, x2] or [x1, x2] [tl, tr]
    // [tu, td] [y1, y2] or [y1, y2] [tu, td]
    if (tr < x1 or x2 < tl or td < y1 or y2 < tu) {
      return 0;
    }
    // [x1 [tl, tr] x2] and [y1 [tu, td] y2]
    if (x1 <= tl and tr <= x2 and y1 <= tu and td <= y2) {
      return val;
    }
    return (a ? a->query(x1, x2, y1, y2) : 0) +
           (b ? b->query(x1, x2, y1, y2) : 0) +
           (c ? c->query(x1, x2, y1, y2) : 0) +
           (d ? d->query(x1, x2, y1, y2) : 0);
  }
};

// 1048576
// 117117

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 << 22) - 1, 0, (1 << 22) - 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(0, x, 0, 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