結果

問題 No.728 ギブ and テイク
コンテスト
ユーザー 0w1
提出日時 2018-08-29 10:47:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,098 ms / 3,000 ms
コード長 1,971 bytes
コンパイル時間 2,018 ms
コンパイル使用メモリ 188,972 KB
実行使用メモリ 223,616 KB
最終ジャッジ日時 2024-07-22 11:04:06
合計ジャッジ時間 12,188 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct Pst {
  int cnt;
  Pst *lc, *rc;
  Pst() : cnt(0), lc(nullptr), rc(nullptr) {}
  Pst(const Pst &oth) : cnt(oth.cnt), lc(oth.lc), rc(oth.rc) {}
  static Pst* modify(Pst *t, int lb, int rb, int k, int v) {
    Pst *n = new Pst(*t);
    if (rb - lb == 1) return n->cnt += v, n;
    int mb = lb + rb >> 1;
    if (k < mb) n->lc = modify(t->lc, lb, mb, k, v);
    else n->rc = modify(t->rc, mb, rb, k, v);
    n->cnt = n->lc->cnt + n->rc->cnt;
    return n;
  }
  static Pst* build(int lb, int rb) {
    Pst *t = new Pst;
    if (rb - lb == 1) return t;
    int mb = lb + rb >> 1;
    t->lc = build(lb, mb);
    t->rc = build(mb, rb);
    return t;
  }
};

signed main() {
  ios::sync_with_stdio(false);

  int N;
  cin >> N;

  vector<int> A(N);
  for (int i = 0; i < N; ++i) cin >> A[i];

  vector<int> L(N), R(N);
  for (int i = 0; i < N; ++i) cin >> L[i] >> R[i];

  vector<int> d(N);
  for (int i = 0; i < N; ++i) d[i] = A[i] + R[i];
  sort(d.begin(), d.end());
  d.erase(unique(d.begin(), d.end()), d.end());
  map<int, int> mp;
  for (int i = 0; i < d.size(); ++i) mp[d[i]] = i;

  vector<Pst *> sts(N + 1);
  sts[0] = Pst::build(0, d.size());
  for (int i = 0; i < N; ++i) sts[i + 1] = Pst::modify(sts[i], 0, d.size(), mp[A[i] + R[i]], 1);

  long long ans = 0;
  for (int i = 1; i < N; ++i) {
    int ver_lb = lower_bound(A.begin(), A.end(), A[i] - L[i]) - A.begin();
    int key_lb = lower_bound(d.begin(), d.end(), A[i]) - d.begin();
    function<int(Pst *, Pst *, int, int, int, int)> dfs =
        [&](Pst *vl, Pst *vr, int lb, int rb, int ql, int qr) {
          if (qr <= lb || rb <= ql) return 0;
          if (ql <= lb && rb <= qr) return vr->cnt - vl->cnt;
          int mb = lb + rb >> 1;
          return dfs(vl->lc, vr->lc, lb, mb, ql, qr) + dfs(vl->rc, vr->rc, mb, rb, ql, qr);
        };
    ans += dfs(sts[ver_lb], sts[i], 0, d.size(), key_lb, d.size());
  }

  cout << ans << endl;

  return 0;
}
0