結果
| 問題 |
No.1919 Many Monster Battles
|
| コンテスト | |
| ユーザー |
 SSRS
|
| 提出日時 | 2022-04-29 23:08:58 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,468 bytes |
| コンパイル時間 | 3,200 ms |
| コンパイル使用メモリ | 233,820 KB |
| 最終ジャッジ日時 | 2025-01-28 23:53:04 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 10 TLE * 22 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
const long long INF = 2000000001;
const long long MOD = 1000000007;
//https://judge.yosupo.jp/submission/86618
template<class T, T (*op)(T, T), T (*e)()>
struct SegmentTree{
int size;
vector<T> seg;
SegmentTree(vector<T> v): size((int)v.size()), seg(move(v)){
seg.insert(seg.begin(), size, T{});
for(int i = size; --i >= 1; ) seg[i] = op(seg[i << 1], seg[i << 1 | 1]);
}
void set(int i, int d, T x){
assert(0 <= i && i < size);
i += size;
seg[i] = x;
while(void(i >>= 1), d--) seg[i] = op(seg[i << 1], seg[i << 1 | 1]);
}
T get(int l, int r) const {
assert(0 <= l && l <= r && r <= size);
l += size;
r += size;
T ans = e();
while(l < r){
if(l & 1) ans = op(ans, seg[l++]);
if(r & 1) ans = op(ans, seg[--r]);
l >>= 1;
r >>= 1;
}
return ans;
}
};
template<class T, T (*op)(T, T), T (*e)()>
struct SegmentTree2D{
using Key = int;
using key_type = pair<Key, Key>;
using value_type = pair<key_type, T>;
using Seg = SegmentTree<T, op, e>;
int size = 1, lg_size = 0;
vector<vector<key_type>> keys;
vector<Seg> seg;
static constexpr auto comp_y = [](const key_type& a, const key_type& b){ return tie(a.second, a.first) < tie(b.second, b.first); };
SegmentTree2D(vector<value_type> v){
sort(v.begin(), v.end(), [](value_type& a, value_type& b){ return a.first < b.first; });
for(int i = 1; i < (int)v.size(); i++) assert(v[i - 1].first < v[i].first);
while(size < v.size()){
size <<= 1;
lg_size++;
}
v.resize(size, pair{pair{INT_MAX, INT_MAX}, e()});
keys.resize(lg_size + 1);
seg.reserve(lg_size + 1);
for(int d = 0; ; d++){
// copy
auto& Y = keys[d];
vector<T> V;
Y.reserve(size);
V.reserve(size);
for(auto& [key, val] : v){
Y.push_back(key);
V.push_back(val);
}
seg.emplace_back(move(V));
if(d == lg_size) break;
// merge
const int w = 1 << d;
for(int l = 0; l < size; l += w * 2){
auto p = v.begin() + l;
inplace_merge(p, p + w, p + w * 2, [](const value_type& a, const value_type& b){ return tie(a.first.second, a.first.first) < tie(b.first.second, b.first.first); });
}
}
}
void set_inner(int d, int i, key_type key, T val){
auto& Y = keys[d];
int l = i << d, r = (i + 1) << d;
seg[d].set(lower_bound(Y.begin() + l, Y.begin() + r - 1, key, comp_y) - Y.begin(), d, val);
}
void set(key_type key, T val){
auto& X = keys[0];
int i = lower_bound(X.begin(), X.end(), key) - X.begin();
assert(i < size && X[i] == key);
for(int d = 0; d <= lg_size; d++, i >>= 1) set_inner(d, i, key, val);
}
void set(Key x, Key y, T val){
set({x, y}, val);
}
T get(key_type key) const {
auto& X = keys[0];
int i = lower_bound(X.begin(), X.end(), key) - X.begin();
assert(i < size && X[i] == key);
return seg[0].seg[size + i];
}
T get(Key x, Key y) const {
return get({x, y});
}
T get_inner(int d, int i, key_type y1, key_type y2) const {
auto& Y = keys[d];
int l = i << d, r = (i + 1) << d;
l = lower_bound(Y.begin() + l, Y.begin() + r, y1, comp_y) - Y.begin();
r = upper_bound(Y.begin() + l, Y.begin() + r, y2, comp_y) - Y.begin();
return seg[d].get(l, r);
}
T get(key_type L, key_type R) const {
assert(L.first <= R.first);
assert(L.second <= R.second);
auto& X = keys[0];
int l = lower_bound(X.begin(), X.end(), L) - X.begin();
int r = upper_bound(X.begin(), X.end(), R) - X.begin();
T ans = e();
for(int d = 0; l < r; d++, l >>= 1, r >>= 1){
if(l & 1) ans = op(ans, get_inner(d, l++, L, R));
if(r & 1) ans = op(ans, get_inner(d, --r, L, R));
}
return ans;
}
/// [x1, x2] * [y1, y2]
T get(int x1, int x2, int y1, int y2) const {
return get({x1, y1}, {x2, y2});
}
};
int op(int a, int b){ return a + b; }
int e(){ return 0; }
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;
}
vector<pair<pair<int, int>, int>> C1(N), C2(N);
for (int j = 0; j < N; j++){
C1[j] = make_pair(make_pair(j, a[j] - b[j]), 0);
C2[j] = make_pair(make_pair(j, a[j] + b[j]), 0);
}
SegmentTree2D<int, op, e> ST1(C1);
SegmentTree2D<int, op, e> ST2(C2);
for (int j = 0; j < N; j++){
int p = id[j];
if (p > 0){
int cnt1 = ST1.get(0, p - 1, -INF, a[p] - b[p] - 1);
ans[i] += (long long) a[p] * cnt1 % MOD;
}
if (p < N - 1){
int cnt2 = ST2.get(p + 1, N - 1, a[p] + b[p] + 1, INF);
ans[i] += MOD - (long long) a[p] * cnt2 % MOD;
}
ST1.set(p, a[p] - b[p], 1);
ST2.set(p, a[p] + b[p], 1);
}
for (int j = 0; j < N; j++){
ST1.set(j, a[j] - b[j], 0);
ST2.set(j, a[j] + b[j], 0);
}
for (int j = N - 1; j >= 0; j--){
int p = id[j];
if (p > 0){
int cnt1 = ST2.get(0, p - 1, -INF, a[p] + b[p] - 1);
ans[i] += (long long) a[p] * cnt1 % MOD;
}
if (p < N - 1){
int cnt2 = ST1.get(p + 1, N - 1, a[p] - b[p] + 1, INF);
ans[i] += MOD - (long long) a[p] * cnt2 % MOD;
}
ST1.set(p, a[p] - b[p], 1);
ST2.set(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;
}