結果

問題 No.728 ギブ and テイク
ユーザー ei1333333ei1333333
提出日時 2018-08-24 22:14:17
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2,144 ms / 3,000 ms
コード長 4,417 bytes
コンパイル時間 3,168 ms
コンパイル使用メモリ 232,456 KB
実行使用メモリ 265,476 KB
最終ジャッジ日時 2023-09-05 12:07:50
合計ジャッジ時間 18,263 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,384 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 3 ms
4,380 KB
testcase_13 AC 65 ms
17,916 KB
testcase_14 AC 109 ms
20,896 KB
testcase_15 AC 42 ms
11,484 KB
testcase_16 AC 97 ms
20,116 KB
testcase_17 AC 90 ms
19,556 KB
testcase_18 AC 1,354 ms
151,508 KB
testcase_19 AC 1,462 ms
155,704 KB
testcase_20 AC 1,910 ms
253,324 KB
testcase_21 AC 1,584 ms
159,540 KB
testcase_22 AC 499 ms
72,448 KB
testcase_23 AC 289 ms
41,004 KB
testcase_24 AC 1,173 ms
140,384 KB
testcase_25 AC 1,153 ms
140,220 KB
testcase_26 AC 513 ms
71,480 KB
testcase_27 AC 2,144 ms
265,476 KB
testcase_28 AC 753 ms
265,424 KB
testcase_29 AC 2 ms
4,384 KB
testcase_30 AC 2 ms
4,380 KB
testcase_31 AC 1 ms
4,380 KB
testcase_32 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

template< class T >
struct BinaryIndexedTree {
  vector< T > data;

  BinaryIndexedTree(int sz) {
    data.assign(++sz, 0);
  }

  T sum(int k) {
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  void add(int k, T x) {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};

template< typename structure_t, typename get_t, typename update_t >
struct SegmentTree2DCompressed {

  using merge_f = function< get_t(get_t, get_t) >;
  using range_get_f = function< get_t(structure_t &, int, int) >;
  using update_f = function< void(structure_t &, int, update_t) >;

  int sz;
  vector< structure_t > seg;
  const merge_f f;
  const range_get_f g;
  const update_f h;
  const get_t identity;
  vector< vector< int > > LL, RR;
  vector< vector< int > > beet;

  SegmentTree2DCompressed(int n, const merge_f &f, const range_get_f &g, const update_f &h, const get_t &identity)
      : f(f), g(g), h(h), identity(identity) {
    sz = 1;
    while(sz < n) sz <<= 1;
    beet.resize(2 * sz);
    LL.resize(2 * sz);
    RR.resize(2 * sz);
  }

  void update(int a, int x, update_t z, int k, int l, int r) {
    if(r <= a || a + 1 <= l) return;
    if(a <= l && r <= a + 1) return h(seg[k], x, z);
    update(a, LL[k][x], z, 2 * k + 0, l, (l + r) >> 1);
    update(a, RR[k][x], z, 2 * k + 1, (l + r) >> 1, r);
    return h(seg[k], x, z);
  }

  void update(int x, int y, update_t z) {
    y = lower_bound(begin(beet[1]), end(beet[1]), y) - begin(beet[1]);
    return update(x, y, z, 1, 0, sz);
  }

  get_t query(int a, int b, int x, int y, int k, int l, int r) {
    if(a >= r || b <= l) return identity;
    if(a <= l && r <= b) return g(seg[k], x, y);
    return f(query(a, b, LL[k][x], LL[k][y], 2 * k + 0, l, (l + r) >> 1),
             query(a, b, RR[k][x], RR[k][y], 2 * k + 1, (l + r) >> 1, r));
  }

  get_t query(int a, int b, int x, int y) {
    x = lower_bound(begin(beet[1]), end(beet[1]), x) - begin(beet[1]);
    y = lower_bound(begin(beet[1]), end(beet[1]), y) - begin(beet[1]);
    return query(a, b, x, y, 1, 0, sz);
  }

  void build() {
    for(int k = (int) beet.size() - 1; k >= sz; k--) {
      sort(begin(beet[k]), end(beet[k]));
      beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k]));
    }
    for(int k = sz - 1; k > 0; k--) {
      beet[k].resize(beet[2 * k + 0].size() + beet[2 * k + 1].size());
      merge(begin(beet[2 * k + 0]), end(beet[2 * k + 0]), begin(beet[2 * k + 1]), end(beet[2 * k + 1]), begin(beet[k]));
      beet[k].erase(unique(begin(beet[k]), end(beet[k])), end(beet[k]));
      LL[k].resize(beet[k].size() + 1);
      RR[k].resize(beet[k].size() + 1);
      int tail1 = 0, tail2 = 0;
      for(int i = 0; i < beet[k].size(); i++) {
        while(tail1 < beet[2 * k + 0].size() && beet[2 * k + 0][tail1] < beet[k][i]) ++tail1;
        while(tail2 < beet[2 * k + 1].size() && beet[2 * k + 1][tail2] < beet[k][i]) ++tail2;
        LL[k][i] = tail1, RR[k][i] = tail2;
      }
      LL[k][beet[k].size()] = (int) beet[2 * k + 0].size();
      RR[k][beet[k].size()] = (int) beet[2 * k + 1].size();
    }
    for(int k = 0; k < beet.size(); k++) {
      seg.emplace_back(structure_t(beet[k].size()));
    }
  }

  void preupdate(int x, int y) {
    beet[x + sz].push_back(y);
  }
};


int main() {
  int N;

  int L[300000], R[300000];

  scanf("%d", &N);
  vector< int > A(N);
  for(int i = 0; i < N; i++) scanf("%d", &A[i]);
  for(int i = 0; i < N; i++) scanf("%d %d", &L[i], &R[i]);
  vector< int > xs;
  for(int i = 0; i < N; i++) xs.push_back(A[i] + R[i]);
  sort(begin(xs), end(xs));
  xs.erase(unique(begin(xs), end(xs)), end(xs));

  using BIT = BinaryIndexedTree< int >;
  auto f = [](int x, int y) { return x + y; };
  auto g = [](BIT &k, int x, int y) { return k.sum(y - 1) - k.sum(x - 1); };
  auto h = [](BIT &k, int x, int y) { k.add(x, y); };
  SegmentTree2DCompressed< BIT, int, int > seg(xs.size(), f, g, h, 0);
  for(int j = 0; j < N; j++) {
    seg.preupdate(lower_bound(begin(xs), end(xs), A[j] + R[j]) - begin(xs), A[j]);
  }
  seg.build();
  int64 ret = 0;
  for(int j = 0; j < N; j++) {
    ret += seg.query(lower_bound(begin(xs), end(xs), A[j]) - begin(xs), xs.size(), A[j] - L[j], numeric_limits< int >::max());
    seg.update(lower_bound(begin(xs), end(xs), A[j] + R[j]) - begin(xs), A[j], 1);
  }
  printf("%lld\n", ret);
}
0