Submission #1173585

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

examination

#include <bits/stdc++.h>

// struct SegmentTree {
// public:
//   std::vector<int> seg;
//   int n;

//   SegmentTree(int n) : n(n) { seg.resize(2 * n); }

//   void add(int idx, int del) {
//     for (seg[idx += n] += del; idx > 1; idx /= 2) {
//       seg[idx / 2] = seg[idx] + seg[idx ^ 1];
//     }
//   }

//   int query(int l, int r) {
//     int ans = 0;
//     for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
//       if (l & 1) {
//         ans += seg[l++];
//       }
//       if (r & 1) {
//         ans += seg[--r];
//       }
//     }
//     return ans;
//   }
// };

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);
  int min_a = 1e9, max_a = 0, min_b = 1e9, max_b = 0;
  for (auto &[s, t] : a) {
    std::cin >> s >> t;
    min_a = std::min(min_a, s);
    max_a = std::max(max_a, s);
    min_b = std::min(min_b, t);
    max_b = std::max(max_b, t);
  }
  std::sort(a.begin(), a.end(),
            [&](std::pair<int, int> p1, std::pair<int, int> p2) {
              return p1.first + p1.second < p2.first + p2.second;
            });
  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});
  }

  std::vector<int> ans(q);

  auto dnc = [&](auto &&self, std::vector<std::pair<int, int>>::iterator beg,
                 std::vector<std::pair<int, int>>::iterator end,
                 std::vector<Query>::iterator q_beg,
                 std::vector<Query>::iterator q_end, int s_a, int e_a, int s_b,
                 int e_b, int del) {
    if (q_beg >= q_end) {
      return;
    }
    if (s_a == e_a and s_b == e_b) {
      for (auto it = q_beg; it != q_end; ++it) {
        // int v = beg - a.begin();
        // int low = beg - a.begin(), high = end - a.begin();
        // while (low <= high) {
        //   int mid = (low + high) / 2;
        //   if (a[mid].first + a[mid].second >= it->z) {
        //     v = mid;
        //     high = mid - 1;
        //   } else {
        //     low = mid + 1;
        //   }
        // }
        // if (a[v].first + a[v].second >= it->z) {
        //   ans[it->i] = end - a.begin() - v + del;
        // }
        ans[it->i] = end - beg + del;
      }
      return;
    }
    if (s_a < e_a) {
      int m_a = (s_a + e_a) / 2;
      auto pred1 = [&](const std::pair<int, int> &p) { return p.first <= m_a; };
      auto pred2 = [&](const Query &q) { return q.x <= m_a; };
      auto a_m = std::partition(a.begin(), a.end(), pred1);
      auto q_m = std::partition(queries.begin(), queries.end(), pred2);
      self(self, beg, a_m, q_beg, q_m, s_a, m_a, s_b, e_b, del + end - a_m);
      self(self, a_m, end, q_m, q_end, m_a + 1, e_a, s_b, e_b, del);
      return;
    } else {
      int m_b = (s_b + e_b) / 2;
      auto pred1 = [&](const std::pair<int, int> &p) {
        return p.second <= m_b;
      };
      auto pred2 = [&](const Query &q) { return q.y <= m_b; };
      auto a_m = std::partition(a.begin(), a.end(), pred1);
      auto q_m = std::partition(queries.begin(), queries.end(), pred2);
      self(self, beg, a_m, q_beg, q_m, s_a, e_a, s_b, m_b, del + end - a_m);
      self(self, a_m, end, q_m, q_end, s_a, e_a, m_b + 1, e_b, del);
    }
  };
  dnc(dnc, a.begin(), a.end(), queries.begin(), queries.end(), min_a, max_a,
      min_b, max_b, 0);

  for (auto &i : ans) {
    std::cout << i << '\n';
  }
}

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