結果

問題 No.728 ギブ and テイク
ユーザー ei1333333ei1333333
提出日時 2018-08-24 22:14:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,945 ms / 3,000 ms
コード長 4,417 bytes
コンパイル時間 2,611 ms
コンパイル使用メモリ 225,596 KB
最終ジャッジ日時 2025-01-06 12:35:03
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:113:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  113 |   scanf("%d", &N);
      |   ~~~~~^~~~~~~~~~
main.cpp:115:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  115 |   for(int i = 0; i < N; i++) scanf("%d", &A[i]);
      |                              ~~~~~^~~~~~~~~~~~~
main.cpp:116:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  116 |   for(int i = 0; i < N; i++) scanf("%d %d", &L[i], &R[i]);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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