Submission #1173616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173616		avighna	Examination (JOI19_examination)	C++20	0 / 100	3098 ms	79820 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);
  }
};

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 qt(0, (1 << 20) - 1, 0, (1 << 20) - 1);
  for (auto &[s, t] : a) {
    std::cin >> s >> t;
    // all queries <= s and <= t are valid
    qt.add(0, 0, 1);
    qt.add(0, t + 1, -1);
    qt.add(s + 1, 0, -1);
    qt.add(s + 1, t + 1, 1);
  }
  struct Query {
    int x, y, z;
    int i;
  };
  std::vector<Query> queries;
  for (int i = 0, x, y, z; i < q; ++i) {
    std::cin >> x >> y >> z;
    queries.push_back({x, y, z, i});
  }

  for (auto &[x, y, z, i] : queries) {
    int ans = qt.query(0, x, 0, y);
    std::cout << ans << '\n';
  }
}

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