結果
| 問題 | No.1919 Many Monster Battles |
| ユーザー |
 SSRS
|
| 提出日時 | 2022-04-29 23:02:13 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,519 bytes |
| コンパイル時間 | 2,122 ms |
| コンパイル使用メモリ | 191,712 KB |
| 実行使用メモリ | 199,200 KB |
| 最終ジャッジ日時 | 2024-06-29 04:40:32 |
| 合計ジャッジ時間 | 6,853 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 10 TLE * 1 -- * 21 |
ソースコード
#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;}