#757150 (C++14) No.1919 Many Monster Battles

提出ソース

結果

問題	No.1919 Many Monster Battles
ユーザー	SSRS
提出日時	2022-04-29 23:02:13
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	5,519 bytes
コンパイル時間	2,117 ms
コンパイル使用メモリ	189,080 KB
実行使用メモリ	196,504 KB
最終ジャッジ日時	2023-09-11 14:28:00
合計ジャッジ時間	6,846 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 196,504 KB
testcase_01	AC	2 ms 4,384 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	30 ms 4,380 KB
testcase_04	AC	29 ms 4,376 KB
testcase_05	AC	29 ms 4,380 KB
testcase_06	AC	29 ms 4,380 KB
testcase_07	AC	30 ms 4,376 KB
testcase_08	AC	30 ms 4,376 KB
testcase_09	AC	30 ms 4,380 KB
testcase_10	AC	30 ms 4,380 KB
testcase_11	AC	30 ms 4,380 KB
testcase_12	AC	30 ms 4,376 KB
testcase_13	TLE	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
const long long INF = 2000000001;
const long long MOD = 1000000007;
template <typename T>
struct segment_tree_2d{
  vector<pair<int, int>> pos;
  vector<int> X;
  vector<vector<int>> Y;
  int N;
  vector<int> N2;
  vector<vector<T>> ST;
  function<T(T, T)> f;
  T E;
  segment_tree_2d(function<T(T, T)> f, T E): f(f), E(E){
  }
  void add(int x, int y){
    pos.push_back(make_pair(x, y));
    X.push_back(x);
  }
  void build(){
    int cnt = pos.size();
    sort(X.begin(), X.end());
    X.erase(unique(X.begin(), X.end()), X.end());
    int cnt2 = X.size();
    N = 1;
    while (N < cnt2){
      N *= 2;
    }
    Y = vector<vector<int>>(N * 2 - 1);
    for (int i = 0; i < cnt; i++){
      int p = lower_bound(X.begin(), X.end(), pos[i].first) - X.begin();
      p += N - 1;
      Y[p].push_back(pos[i].second);
      while (p > 0){
        p = (p - 1) / 2;
        Y[p].push_back(pos[i].second);
      }
    }
    N2 = vector<int>(N * 2 - 1, 0);
    ST = vector<vector<T>>(N * 2 - 1);
    for (int i = 0; i < N * 2 - 1; i++){
      if (!Y[i].empty()){
        sort(Y[i].begin(), Y[i].end());
        Y[i].erase(unique(Y[i].begin(), Y[i].end()), Y[i].end());
        int cnt3 = Y[i].size();
        N2[i] = 1;
        while (N2[i] < cnt3){
          N2[i] *= 2;
        }
        ST[i] = vector<T>(N2[i] * 2 - 1);
      }
    }
  }
  T get(int x, int y){
    int p1 = lower_bound(X.begin(), X.end(), x) - X.begin();
    p1 += N - 1;
    int p2 = lower_bound(Y[p1].begin(), Y[p1].end(), y) - Y[p1].begin();
    p2 += N2[p1] - 1;
    return ST[p1][p2];
  }
  void update2(int i, int j, T x){
    j += N2[i] - 1;
    ST[i][j] = x;
    while (j > 0){
      j = (j - 1) / 2;
      ST[i][j] = f(ST[i][j * 2 + 1], ST[i][j * 2 + 2]);
    }
  }
  void update(int i, int j, T x){
    int p1 = lower_bound(X.begin(), X.end(), i) - X.begin();
    p1 += N - 1;
    int p2 = lower_bound(Y[p1].begin(), Y[p1].end(), j) - Y[p1].begin();
    update2(p1, p2, x);
    while (p1 > 0){
      p1 = (p1 - 1) / 2;
      p2 = lower_bound(Y[p1].begin(), Y[p1].end(), j) - Y[p1].begin();
      T x2 = 0;
      int pl = lower_bound(Y[p1 * 2 + 1].begin(), Y[p1 * 2 + 1].end(), j) - Y[p1 * 2 + 1].begin();
      if (pl < Y[p1 * 2 + 1].size()){
        if (Y[p1 * 2 + 1][pl] == j){
          x2 += ST[p1 * 2 + 1][N2[p1 * 2 + 1] - 1 + pl];
        }
      }
      int pr = lower_bound(Y[p1 * 2 + 2].begin(), Y[p1 * 2 + 2].end(), j) - Y[p1 * 2 + 2].begin();
      if (pr < Y[p1 * 2 + 2].size()){
        if (Y[p1 * 2 + 2][pr] == j){
          x2 += ST[p1 * 2 + 2][N2[p1 * 2 + 2] - 1 + pr];
        }
      }
      update2(p1, p2, x2);
    }
  }
  T query1(int id, int L, int R, int i, int l, int r){
    if (r <= L || R <= l){
      return E;
    } else if (L <= l && r <= R){
      return ST[id][i];
    } else {
      int m = (l + r) / 2;
      return f(query1(id, L, R, i * 2 + 1, l, m), query1(id, L, R, i * 2 + 2, m, r));
    }
  }
  T query2(int U, int D, int L, int R, int i, int u, int d){
    if (d <= U || D <= u){
      return E;
    } else if (U <= u && d <= D){
      int l = lower_bound(Y[i].begin(), Y[i].end(), L) - Y[i].begin();
      int r = lower_bound(Y[i].begin(), Y[i].end(), R) - Y[i].begin();
      return query1(i, l, r, 0, 0, N2[i]);
    } else {
      int m = (u + d) / 2;
      return f(query2(U, D, L, R, i * 2 + 1, u, m), query2(U, D, L, R, i * 2 + 2, m, d));
    }
  }
  T query(int U, int D, int L, int R){
    int u = lower_bound(X.begin(), X.end(), U) - X.begin();
    int d = lower_bound(X.begin(), X.end(), D) - X.begin();
    return query2(u, d, L, R, 0, 0, N);
  }
};
int op(int x, int y){
  return x + y;
}
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;
    }
    segment_tree_2d<int> ST1(op, 0);
    segment_tree_2d<int> ST2(op, 0);
    for (int j = 0; j < N; j++){
      ST1.add(j, a[j] - b[j]);
      ST2.add(j, a[j] + b[j]);
    }
    ST1.build();
    ST2.build();
    for (int j = 0; j < N; j++){
      int p = id[j];
      int cnt1 = ST1.query(0, p, -INF, a[p] - b[p]);
      ans[i] += (long long) a[p] * cnt1 % MOD;
      int cnt2 = ST2.query(p + 1, N, a[p] + b[p] + 1, INF);
      ans[i] += MOD - (long long) a[p] * cnt2 % MOD;
      ST1.update(p, a[p] - b[p], 1);
      ST2.update(p, a[p] + b[p], 1);
    }
    for (int j = 0; j < N; j++){
      ST1.update(j, a[j] - b[j], 0);
      ST2.update(j, a[j] + b[j], 0);
    }
    for (int j = N - 1; j >= 0; j--){
      int p = id[j];
      int cnt1 = ST2.query(0, p, -INF, a[p] + b[p]);
      ans[i] += (long long) a[p] * cnt1 % MOD;
      int cnt2 = ST1.query(p + 1, N, a[p] - b[p] + 1, INF);
      ans[i] += MOD - (long long) a[p] * cnt2 % MOD;
      ST1.update(p, a[p] - b[p], 1);
      ST2.update(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;
}

yukicoder

結果

テストケース

ソースコード