結果

問題 No.728 ギブ and テイク
ユーザー 0w10w1
提出日時 2018-08-29 10:47:26
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,193 ms / 3,000 ms
コード長 1,971 bytes
コンパイル時間 1,954 ms
コンパイル使用メモリ 186,336 KB
実行使用メモリ 223,688 KB
最終ジャッジ日時 2023-09-29 16:59:41
合計ジャッジ時間 13,206 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,384 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 3 ms
4,376 KB
testcase_13 AC 42 ms
13,644 KB
testcase_14 AC 74 ms
21,408 KB
testcase_15 AC 27 ms
10,696 KB
testcase_16 AC 65 ms
19,352 KB
testcase_17 AC 56 ms
17,792 KB
testcase_18 AC 805 ms
155,832 KB
testcase_19 AC 871 ms
166,260 KB
testcase_20 AC 1,040 ms
194,424 KB
testcase_21 AC 918 ms
175,100 KB
testcase_22 AC 305 ms
67,744 KB
testcase_23 AC 178 ms
43,788 KB
testcase_24 AC 604 ms
128,952 KB
testcase_25 AC 618 ms
128,468 KB
testcase_26 AC 279 ms
65,360 KB
testcase_27 AC 1,193 ms
223,408 KB
testcase_28 AC 590 ms
223,688 KB
testcase_29 AC 1 ms
4,380 KB
testcase_30 AC 2 ms
4,376 KB
testcase_31 AC 1 ms
4,380 KB
testcase_32 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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