けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Round #625 (Div. 1) C. World of Darkraft: Battle for Azathoth (R2000)

セグ木を使って差分更新していく系、解けるけど実装が苦手すぎるので、こういうのをスパッと書けるようになりたい!

問題へのリンク

問題概要

 N 個の武器と、 M 個の盾を持って、 P 体の敵に立ち向かう。あたなは武器の中から 1 個、盾の中から 1 個を選ぶ (初期状態では無限大だけのコインを持っている、そして必ず買わなければならない)。

  • 武器  i は、 a_{i} の攻撃力があって、 ca_{i} のコインを消費する
  •  i は、 b_{i} の防御力があって、 cb_{i} のコインを消費する
  •  i は、 x_{i} の防御力と  y_{i} の攻撃力があって、倒せば  z_{i} だけのコインが手に入る

手持ちの武器と盾で敵を倒せる条件は

  • 武器の攻撃力が、敵の防御力より strict に大きい
  • 盾の防御力が、敵の攻撃力より strict に大きい

である。コインの増加分の最大値を求めよ (たとえば購入した武器と盾で敵を十分に倒せなかった場合には負の値になりうる)

制約

  •  N, M, P \le 10^{5}

考えたこと

ふと思うことは、「武器をどれを選ぶか」と「盾をどれを選ぶか」を決めると、倒せる敵の集合が定まるので、答えが決まるわけだ。

しかしこれでは  O(NM) 通り考えることになるのでダメ。こういうシチュエーションでは、まず「武器か盾かどちらか一方の値を固定したときに、盾の選択に伴う最適解」を素早く求めることができないかを考えることになる。今回はどちらを固定しても本質的な違いはないので、武器を固定して考える。

武器を固定すると...

  1. まず武器の攻撃力より低い防御力の敵のみを抜き出して
  2. そのうち、各盾について、倒せる敵から得られるリターンの合計値が素早くわかれば...

という雰囲気の考察になる。ここで 1 の「低い防御力の敵を抜き出して」という操作を実現するためには、あらかじめ「敵を防御力が低い順にソートしておく」という風にしておくとよい。さらに、2 の処理を実現するためには敵が 1 体ずつ追加されていった方が考えやすい。そこで、次のように考えることにする。

あらかじめ各盾についての、選んだ場合のコスト (- 敵を倒すリターン) を格納した配列を用意して、それを Starry Sky Tree に乗せておく。

  • 敵を 1 体ずつ追加する
  • このとき、まず追加された敵をすべて倒せる武器 (のうち、コストが最も低いもの) を用意する
  • 追加された敵の攻撃力を上回る盾について、その敵を倒して得られるリターン分を引いておく
  • その処理後の Starry Sky Tree 全体の最小値を求める
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

// Segment Tree
template<class Monoid, class Action> struct SegTree {
    using FuncMonoid = function< Monoid(Monoid, Monoid) >;
    using FuncAction = function< void(Monoid&, Action) >;
    using FuncLazy = function< void(Action&, Action) >;
    FuncMonoid FM;
    FuncAction FA;
    FuncLazy FL;
    Monoid UNITY_MONOID;
    Action UNITY_LAZY;
    int SIZE, HEIGHT;
    vector<Monoid> dat;
    vector<Action> lazy;
    
    SegTree() { }
    SegTree(int n, const FuncMonoid fm, const FuncAction fa, const FuncLazy fl,
            const Monoid &unity_monoid, const Action &unity_lazy)
    : FM(fm), FA(fa), FL(fl), UNITY_MONOID(unity_monoid), UNITY_LAZY(unity_lazy) {
        SIZE = 1; HEIGHT = 0;
        while (SIZE < n) SIZE <<= 1, ++HEIGHT;
        dat.assign(SIZE * 2, UNITY_MONOID);
        lazy.assign(SIZE * 2, UNITY_LAZY);
    }
    void init(int n, const FuncMonoid fm, const FuncAction fa, const FuncLazy fl,
              const Monoid &unity_monoid, const Action &unity_lazy) {
        FM = fm; FA = fa; FL = fl;
        UNITY_MONOID = unity_monoid; UNITY_LAZY = unity_lazy;
        SIZE = 1; HEIGHT = 0;
        while (SIZE < n) SIZE <<= 1, ++HEIGHT;
        dat.assign(SIZE * 2, UNITY_MONOID);
        lazy.assign(SIZE * 2, UNITY_LAZY);
    }
    
    /* set, a is 0-indexed */
    void set(int a, const Monoid &v) { dat[a + SIZE] = v; }
    void build() {
        for (int k = SIZE - 1; k > 0; --k)
            dat[k] = FM(dat[k*2], dat[k*2+1]);
    }
    
    /* update [a, b) */
    inline void evaluate(int k) {
        if (lazy[k] == UNITY_LAZY) return;
        if (k < SIZE) FL(lazy[k*2], lazy[k]), FL(lazy[k*2+1], lazy[k]);
        FA(dat[k], lazy[k]);
        lazy[k] = UNITY_LAZY;
    }
    inline void update(int a, int b, const Action &v, int k, int l, int r) {
        evaluate(k);
        if (a <= l && r <= b)  FL(lazy[k], v), evaluate(k);
        else if (a < r && l < b) {
            update(a, b, v, k*2, l, (l+r)>>1), update(a, b, v, k*2+1, (l+r)>>1, r);
            dat[k] = FM(dat[k*2], dat[k*2+1]);
        }
    }
    inline void update(int a, int b, const Action &v) { update(a, b, v, 1, 0, SIZE); }
    
    /* get [a, b) */
    inline Monoid get(int a, int b, int k, int l, int r) {
        evaluate(k);
        if (a <= l && r <= b)
            return dat[k];
        else if (a < r && l < b)
            return FM(get(a, b, k*2, l, (l+r)>>1), get(a, b, k*2+1, (l+r)>>1, r));
        else
            return UNITY_MONOID;
    }
    inline Monoid get(int a, int b) { return get(a, b, 1, 0, SIZE); }
    inline Monoid operator [] (int a) { return get(a, a+1); }
    
    /* debug */
    void print() {
        for (int i = 0; i < SIZE; ++i) { cout << (*this)[i]; if (i != SIZE) cout << ","; }
        cout << endl;
    }
};

const long long INF = 1LL<<60;
using pll = pair<long long, long long>;
using tup = pair<pll, long long>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 入力とソート
    int N, M, P;
    cin >> N >> M >> P;
    vector<pll> at(N), de(M);
    vector<tup> teki(P);
    long long mi_at = INF, mi_de = INF;
    for (int i = 0; i < N; ++i) {
        cin >> at[i].first >> at[i].second;
        chmin(mi_at, at[i].second);
    }
    for (int i = 0; i < M; ++i) {
        cin >> de[i].first >> de[i].second;
        chmin(mi_de, de[i].second);
    }
    for (int i = 0; i < P; ++i) {
        cin >> teki[i].first.first >> teki[i].first.second >> teki[i].second;
    }
    at.push_back(pll(INF, INF)), de.push_back(pll(INF, INF));
    sort(at.begin(), at.end());
    sort(de.begin(), de.end());
    sort(teki.begin(), teki.end());
    for (int i = at.size()-2; i >= 0; --i) chmin(at[i].second, at[i+1].second);

    // セグ木
    auto fm = [](long long a, long long b) { return min(a, b); };
    auto fa = [](long long &a, long long d) { a += d; };
    auto fl = [](long long &d, long long e) { d += e; };
    SegTree<long long, long long> seg(de.size() + 5, fm, fa, fl, INF, 0);

    // 順に調べる
    long long res = mi_at + mi_de; // 敵をまったく倒さない場合
    for (int i = 0; i < de.size(); ++i) seg.set(i, de[i].second);
    seg.build();
    for (int i = 0; i < teki.size(); ++i) {
        auto it = upper_bound(at.begin(), at.end(), pll(teki[i].first.first, INF));
        long long attack_cost = it->second;
        auto index = upper_bound(de.begin(), de.end(), pll(teki[i].first.second, INF)) - de.begin();
        seg.update(index, de.size() + 5, -teki[i].second);
        long long val = seg.get(0, de.size() + 5);
        chmin(res, attack_cost + val);
    }
    cout << -res << endl;
}