#757180 (C++17) No.1919 Many Monster Battles

提出ソース

結果

問題	No.1919 Many Monster Battles
ユーザー	SSRS
提出日時	2022-04-29 23:08:58
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	6,468 bytes
コンパイル時間	3,227 ms
コンパイル使用メモリ	243,348 KB
実行使用メモリ	179,972 KB
最終ジャッジ日時	2024-06-29 04:51:13
合計ジャッジ時間	8,168 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 10,752 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	17 ms 5,376 KB
testcase_04	AC	16 ms 5,376 KB
testcase_05	AC	17 ms 5,376 KB
testcase_06	AC	16 ms 5,376 KB
testcase_07	AC	16 ms 5,376 KB
testcase_08	AC	17 ms 5,376 KB
testcase_09	AC	16 ms 5,376 KB
testcase_10	AC	16 ms 5,376 KB
testcase_11	AC	16 ms 5,376 KB
testcase_12	AC	17 ms 5,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;
//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;
}

yukicoder

結果

テストケース

ソースコード