結果

問題 No.776 A Simple RMQ Problem
ユーザー tomatoma
提出日時 2019-10-07 22:39:28
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 564 ms / 3,000 ms
コード長 5,774 bytes
コンパイル時間 1,744 ms
コンパイル使用メモリ 179,468 KB
実行使用メモリ 17,528 KB
最終ジャッジ日時 2024-04-23 01:05:46
合計ジャッジ時間 12,206 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 47 ms
6,940 KB
testcase_03 AC 179 ms
16,628 KB
testcase_04 AC 231 ms
7,168 KB
testcase_05 AC 378 ms
16,692 KB
testcase_06 AC 112 ms
9,944 KB
testcase_07 AC 248 ms
16,784 KB
testcase_08 AC 295 ms
9,924 KB
testcase_09 AC 99 ms
17,136 KB
testcase_10 AC 170 ms
10,160 KB
testcase_11 AC 310 ms
17,312 KB
testcase_12 AC 410 ms
17,424 KB
testcase_13 AC 401 ms
17,340 KB
testcase_14 AC 411 ms
17,336 KB
testcase_15 AC 409 ms
17,408 KB
testcase_16 AC 400 ms
17,528 KB
testcase_17 AC 564 ms
17,452 KB
testcase_18 AC 283 ms
17,424 KB
testcase_19 AC 481 ms
17,404 KB
testcase_20 AC 486 ms
17,336 KB
testcase_21 AC 470 ms
17,504 KB
testcase_22 AC 478 ms
17,444 KB
testcase_23 AC 483 ms
17,404 KB
testcase_24 AC 467 ms
17,340 KB
testcase_25 AC 93 ms
6,940 KB
testcase_26 AC 263 ms
17,400 KB
testcase_27 AC 224 ms
17,356 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;
constexpr ll INF = 1ll << 60;

template<typename Monoid, typename OperatorMonoid = Monoid>
class LazySegmentTree {
private:
    using F = function<Monoid(Monoid, Monoid)>;
    using G = function<Monoid(Monoid, OperatorMonoid, int)>;
    using H = function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>;

    int sz; // 対応する配列の幅
    vector<Monoid> data;
    vector<OperatorMonoid> lazy;
    const F f; // 2区間マージ演算(data-data-ボトムアップマージ)
    const G g; // 要素,作用素マージ演算(lazy->data同位置変換時の、(data,lazy,len)の計算)
    const H h; // 作用素マージ演算　(query->lazyトップダウン伝搬時の、(lazy,query_value)の計算)
    const Monoid M1;          // モノイド単位元　(data単位元)
    const OperatorMonoid OM0; // 作用素単位元 (lazy単位元)

    void propagate(int idx, int len) {
        // 幅lenのlazy[idx]が存在するとき、値を下に流す
        if (lazy[idx] != OM0) {
            if (idx < sz) {
                lazy[(idx << 1) | 0] = h(lazy[(idx << 1) | 0], lazy[idx]);
                lazy[(idx << 1) | 1] = h(lazy[(idx << 1) | 1], lazy[idx]);
            }
            data[idx] = g(data[idx], lazy[idx], len);
            lazy[idx] = OM0;
        }
    }
    Monoid update_impl(int a, int b, const OperatorMonoid& val, int idx, int l, int r) {
        propagate(idx, r - l);
        if (r <= a || b <= l)return data[idx];
        else if (a <= l && r <= b) {
            lazy[idx] = h(lazy[idx], val);
            propagate(idx, r - l);
            return data[idx];
        }
        else return data[idx] = f(
            update_impl(a, b, val, (idx << 1) | 0, l, (l + r) >> 1),
            update_impl(a, b, val, (idx << 1) | 1, (l + r) >> 1, r)
        );
    }
    Monoid query_impl(int a, int b, int idx, int l, int r) {
        propagate(idx, r - l);
        if (r <= a || b <= l)return M1;
        else if (a <= l && r <= b)return data[idx];
        else return f(
            query_impl(a, b, (idx << 1) | 0, l, (l + r) >> 1),
            query_impl(a, b, (idx << 1) | 1, (l + r) >> 1, r)
        );
    }

public:
    // init忘れに注意
    LazySegmentTree(int n, const F f, const G g, const H h,
        const Monoid& M1, const OperatorMonoid OM0)
        :f(f), g(g), h(h), M1(M1), OM0(OM0) {
        sz = 1;
        while (sz < n)sz <<= 1;
        data.assign(2 * sz, M1);
        lazy.assign(2 * sz, OM0);
    }
    void build(const vector<Monoid>& vals) {
        rep(idx, vals.size())data[idx + sz] = vals[idx];
        for (int idx = sz - 1; idx > 0; idx--) {
            data[idx] = f(data[(idx << 1) | 0], data[(idx << 1) | 1]);
        }
    }
    Monoid update(int a, int b, const OperatorMonoid& val) {
        return update_impl(a, b, val, 1, 0, sz);
    }
    Monoid query(int a, int b) {
        return query_impl(a, b, 1, 0, sz);
    }
    Monoid operator[](const int& idx) {
        return query(idx, idx + 1);
    }
};
int main()
{
    // total, left, middle, right
    using ar4 = array<ll, 4>;
    constexpr ar4 arINF = { INF,INF,INF,INF };
    auto f = [](ar4 vl, ar4 vr) {
        if (vl[0] == INF)return vr;
        if (vr[0] == INF)return vl;
        ll mid = vl[3] + vr[1];
        mid = max(mid, *max_element(vl.begin(), vl.end()));
        mid = max(mid, *max_element(vr.begin(), vr.end()));
        auto res = ar4({
            vl[0] + vr[0],
            max(vl[1], vl[0] + vr[1]),
            mid,
            max(vl[3] + vr[0], vr[3])
            });
        return res;
    };
    auto g = [](ar4 data, ll lazy, int len) {
        if (lazy == INF)return data;
        ll info = lazy >= 0 ? lazy * len : lazy;
        return ar4({
            lazy * len,
            info,
            info,
            info
            });
    };
    auto h = [](ll lazy, ll query) {
        return query == INF ? lazy : query;
    };

    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    vector<ar4> b(n);
    rep(i, n) {
        cin >> a[i];
        b[i] = { a[i], a[i],a[i],a[i] };
    }

    LazySegmentTree<ar4, ll> lst(n, f, g, h, arINF, INF);
    lst.build(b);

    while (q--) {
        string type;
        cin >> type;
        if (type == "set") {
            ll i, x;
            cin >> i >> x;
            i--;
            lst.update(i, i + 1, x);
        }
        else {
            ll l1, l2, r1, r2, res;
            cin >> l1 >> l2 >> r1 >> r2;
            l1--; l2--; r1--; r2--;

            // inclusive
            r1 = max(l1, r1);
            l2 = min(r2, l2);
            if (l2 < r1) {
                res = lst.query(l1, l2 + 1)[3]
                    + (l2 + 1 < r1 ? lst.query(l2 + 1, r1)[0] : 0)
                    + lst.query(r1, r2 + 1)[1];
            }
            else {
                ll res1 = lst.query(r1, l2 + 1)[2];
                ll res2 = lst.query(l1, r1)[3] + lst.query(r1, r2 + 1)[1];
                ll res3 = lst.query(r1, l2 + 1)[3] + lst.query(l2 + 1, r2 + 1)[1];
                //auto tmp = lst[2];
                //cerr << "res1: [" << r1 << ", " << l2 << "]" << res1 << endl;
                //cerr << "res2: [" << l1 << ", " << r1 << ", " << r2 << "]"
                //    << res2 << "=" << lst[2][0] << "," << lst[3][0] << endl;
                //cerr << "res3: [" << r1 << ", " << l2 << ", " << r2 << "]" << res3 << endl;
                if (res1 > INF / 2)res1 = -INF;
                if (res2 > INF / 2)res2 = -INF;
                if (res3 > INF / 2)res3 = -INF;
                res = max(res1, max(res2, res3));

            }
            cout << res << endl;
        }
    }
    return 0;

}
0