結果

問題 No.1919 Many Monster Battles
コンテスト
ユーザー SSRS
提出日時 2022-04-29 23:15:08
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,347 bytes
コンパイル時間 2,395 ms
コンパイル使用メモリ 199,128 KB
実行使用メモリ 92,768 KB
最終ジャッジ日時 2024-06-29 04:57:42
合計ジャッジ時間 6,728 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'void Binary_Indexed_Tree_2D<T, S>::build()':
main.cpp:82:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   82 |             auto [x, y] = p;
      |                  ^

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const long long INF = 2000000001;
const long long MOD = 1000000007;
//https://judge.yosupo.jp/submission/79502
template <typename T>
struct Binary_Indexed_Tree {
    vector<T> bit;
    const int n;

    Binary_Indexed_Tree(const vector<T> &v) : n((int)v.size()) {
        bit.resize(n + 1);
        copy(begin(v), end(v), begin(bit) + 1);
        for (int a = 2; a <= n; a <<= 1) {
            for (int b = a; b <= n; b += a) bit[b] += bit[b - a / 2];
        }
    }

    Binary_Indexed_Tree(int n, const T &x) : n(n) {
        bit.resize(n + 1);
        vector<T> v(n, x);
        copy(begin(v), end(v), begin(bit) + 1);
        for (int a = 2; a <= n; a <<= 1) {
            for (int b = a; b <= n; b += a) bit[b] += bit[b - a / 2];
        }
    }

    void add(int i, const T &x) {
        for (i++; i <= n; i += (i & -i)) bit[i] += x;
    }

    void change(int i, const T &x) { add(i, x - query(i, i + 1)); }

    T sum(int i) const {
        T ret = 0;
        for (; i > 0; i -= (i & -i)) ret += bit[i];
        return ret;
    }

    T query(int l, int r) const { return sum(r) - sum(l); }

    T operator[](int i) const { return query(i, i + 1); }

    int lower_bound(T x) const {
        int ret = 0;
        for (int k = 31 - __builtin_clz(n); k >= 0; k--) {
            if (ret + (1 << k) <= n && bit[ret + (1 << k)] < x) x -= bit[ret += (1 << k)];
        }
        return ret;
    }

    int upper_bound(T x) const {
        int ret = 0;
        for (int k = 31 - __builtin_clz(n); k >= 0; k--) {
            if (ret + (1 << k) <= n && bit[ret + (1 << k)] <= x) x -= bit[ret += (1 << k)];
        }
        return ret;
    }
};

template <typename T, typename S> // S は座標の型
struct Binary_Indexed_Tree_2D {
    int n;
    vector<S> xs;
    vector<pair<S, S>> all_points;
    vector<vector<S>> ys;
    vector<Binary_Indexed_Tree<T>> bits;

    Binary_Indexed_Tree_2D() {}

    void insert(const S &x, const S &y) { // 値を変更する箇所を先に全て挿入しておく
        xs.push_back(x);
        all_points.emplace_back(x, y);
    }

    void build() {
        sort(begin(xs), end(xs));
        xs.erase(unique(begin(xs), end(xs)), end(xs));
        n = xs.size();
        ys.resize(n + 1);
        for (auto &p : all_points) {
            auto [x, y] = p;
            int i = lower_bound(begin(xs), end(xs), x) - begin(xs);
            for (i++; i <= n; i += (i & -i)) ys[i].push_back(y);
        }
        for (int i = 0; i <= n; i++) {
            sort(begin(ys[i]), end(ys[i]));
            ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
            bits.emplace_back((int)ys[i].size(), 0);
        }
    }

    void add(const S &x, const S &y, const T &a) {
        int i = lower_bound(begin(xs), end(xs), x) - begin(xs);
        for (i++; i <= n; i += (i & -i)) {
            int j = lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
            bits[i].add(j, a);
        }
    }

    T sum(const S &x, const S &ly, const S &ry) {
        int i = lower_bound(begin(xs), end(xs), x) - begin(xs);
        T ret = 0;
        for (; i > 0; i -= (i & -i)) {
            int lj = lower_bound(begin(ys[i]), end(ys[i]), ly) - begin(ys[i]);
            int rj = lower_bound(begin(ys[i]), end(ys[i]), ry) - begin(ys[i]);
            ret += bits[i].query(lj, rj);
        }
        return ret;
    }

    T query(const S &lx, const S &rx, const S &ly, const S &ry) { return sum(rx, ly, ry) - sum(lx, ly, ry); }
};
int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++){
    cin >> a[i];
  }
  vector<int> b(N);
  for (int i = 0; i < N; i++){
    cin >> b[i];
  }
  vector<long long> ans(2, 0);
  for (int i = 0; i < 2; i++){
    vector<pair<int, int>> P(N);
    for (int j = 0; j < N; j++){
      P[j] = make_pair(a[j], b[j]);
    }
    sort(P.begin(), P.end());
    for (int j = 0; j < N; j++){
      a[j] = P[j].first;
      b[j] = P[j].second;
    }
    vector<pair<int, int>> P2(N);
    for (int j = 0; j < N; j++){
      P2[j] = make_pair(b[j], j);
    }
    sort(P2.begin(), P2.end());
    vector<int> id(N);
    for (int j = 0; j < N; j++){
      id[j] = P2[j].second;
    }
    Binary_Indexed_Tree_2D<int, int> BIT1, BIT2;
    for (int j = 0; j < N; j++){
      BIT1.insert(j, a[j] - b[j]);
      BIT2.insert(j, a[j] + b[j]);
    }
    BIT1.build();
    BIT2.build();
    for (int j = 0; j < N; j++){
      int p = id[j];
      int cnt1 = BIT1.query(0, p, -INF, a[p] - b[p]);
      ans[i] += (long long) a[p] * cnt1 % MOD;
      int cnt2 = BIT2.query(p + 1, N, a[p] + b[p] + 1, INF);
      ans[i] += MOD - (long long) a[p] * cnt2 % MOD;
      BIT1.add(p, a[p] - b[p], 1);
      BIT2.add(p, a[p] + b[p], 1);
    }
    for (int j = 0; j < N; j++){
      BIT1.add(j, a[j] - b[j], -1);
      BIT2.add(j, a[j] + b[j], -1);
    }
    for (int j = N - 1; j >= 0; j--){
      int p = id[j];
      int cnt1 = BIT2.query(0, p, -INF, a[p] + b[p]);
      ans[i] += (long long) a[p] * cnt1 % MOD;
      int cnt2 = BIT1.query(p + 1, N, a[p] - b[p] + 1, INF);
      ans[i] += MOD - (long long) a[p] * cnt2 % MOD;
      BIT1.add(p, a[p] - b[p], 1);
      BIT2.add(p, a[p] + b[p], 1);
    }
    ans[i] %= MOD;
    ans[i] += MOD;
    ans[i] *= 2;
    ans[i] %= MOD;
    swap(a, b);
  }
  cout << ans[0] << ' ' << ans[1] << endl;
}
0