Submission #1367180

#TimeUsernameProblemLanguageResultExecution timeMemory
1367180kunzaZa183Pairs (IOI07_pairs)C++20
0 / 100
195 ms68528 KiB
#include <bits/stdc++.h>
using namespace std;
int main() {
  int b, n, d, m;
  cin >> b >> n >> d >> m;
  if (b == 2) {
    vector<pair<int, int>> vpi(n);
    for (auto &[a, b] : vpi)
      cin >> a >> b;

    auto cmp = [&](pair<int, int> a, pair<int, int> b) {
      return a.first - a.second < b.first - b.second;
    };
    sort(vpi.begin(), vpi.end(), cmp);

    const int mn = 15e4;
    struct nod {
      int val;
      nod *l, *r;
    };
    vector<nod *> vn;
    function<nod *(int, int)> bui = [&](int cl, int cr) {
      nod *n = new nod;
      if (cl != cr) {
        n->l = bui(cl, (cl + cr) / 2);
        n->r = bui((cl + cr) / 2 + 1, cr);
      }
      return n;
    };
    vn.push_back(bui(0, mn));
    function<nod *(nod *, int, int, int, int)> upd = [&](nod *cur, int l, int r,
                                                         int in, int val) {
      nod *n = new nod;
      if (l == r) {
        n->val += val;
        return n;
      }
      int mid = (l + r) / 2;
      if (in <= mid) {
        n->r = cur->r;
        n->l = upd(cur->l, l, mid, in, val);
      } else {
        n->l = cur->l;
        n->r = upd(cur->r, mid + 1, r, in, val);
      }
      n->val = n->l->val + n->r->val;
      return n;
    };
    function<int(nod *, int, int, int, int)> qry = [&](nod *cur, int l, int r,
                                                       int ql, int qr) {
      if (l > qr || r < ql)
        return 0;

      if (ql <= l && r <= qr) {
        return cur->val;
      }

      return qry(cur->l, l, (l + r) / 2, ql, qr) +
             qry(cur->r, (l + r) / 2 + 1, r, ql, qr);
    };

    for (auto [a, b] : vpi) {
      // cout << a << " " << b << "\n";
      vn.push_back(upd(vn.back(), 0, mn, a + b, 1));
    }
    // cout << "\n";

    long long ans = 0;
    for (auto [a, b] : vpi) {
      int rt = upper_bound(vpi.begin(), vpi.end(), make_pair(a + d, b), cmp) -
               vpi.begin(),
          lt = lower_bound(vpi.begin(), vpi.end(), make_pair(a, b + d), cmp) -
               vpi.begin();

      // cout << lt << " " << rt << "\n";

      ans += qry(vn[rt], 0, mn, a + b - d, a + b + d) -
             qry(vn[lt], 0, mn, a + b - d, a + b + d);
      // cout << ans << "\n";
    }

    cout << (ans - n) / 2 << "\n";
  }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...