結果

問題 No.2333 Slime Structure
ユーザー Ricky_ponRicky_pon
提出日時 2023-05-28 16:47:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,197 bytes
コンパイル時間 1,886 ms
コンパイル使用メモリ 152,896 KB
実行使用メモリ 57,156 KB
最終ジャッジ日時 2023-08-27 14:12:35
合計ジャッジ時間 9,999 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 169 ms
36,724 KB
testcase_13 AC 168 ms
36,724 KB
testcase_14 AC 170 ms
36,616 KB
testcase_15 AC 169 ms
36,564 KB
testcase_16 AC 171 ms
36,564 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <string.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <ciso646>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP_OVERLOAD(arg1, arg2, arg3, arg4, NAME, ...) NAME
#define REP3(i, l, r, s)                                               \
    for (int i = int(l), rep3_r = int(r), rep3_s = int(s); i < rep3_r; \
         i += rep3_s)
#define REP2(i, l, r) REP3(i, l, r, 1)
#define REP1(i, n) REP2(i, 0, n)
#define rep(...) REP_OVERLOAD(__VA_ARGS__, REP3, REP2, REP1, )(__VA_ARGS__)
#define repin(i, l, r) for (int i = int(l), repin_r = int(r); i <= repin_r; ++i)

#define RREP_OVERLOAD(arg1, arg2, arg3, arg4, NAME, ...) NAME
#define RREP3(i, l, r, s)                                                      \
    for (int i = int(r) - 1, rrep3_l = int(l), rrep3_s = int(s); i >= rrep3_l; \
         i -= rrep3_s)
#define RREP2(i, l, r) RREP3(i, l, r, 1)
#define RREP1(i, n) RREP2(i, 0, n)
#define rrep(...) RREP_OVERLOAD(__VA_ARGS__, RREP3, RREP2, RREP1, )(__VA_ARGS__)
#define rrepin(i, l, r) \
    for (int i = int(r), rrepin_l = int(l); i >= rrepin_l; --i)

#define fi first
#define se second

#include <atcoder/segtree>

#include <algorithm>
#include <cassert>
#include <vector>

namespace rklib {

template <typename T = int>
struct CoordComp {
   public:
    CoordComp() {}
    CoordComp(std::vector<T> &a) : v(a) { build(); }

    int size() { return v.size(); }

    void add(T x) {
        v.push_back(x);
        built = false;
    }

    void build() {
        std::sort(v.begin(), v.end());
        v.erase(std::unique(v.begin(), v.end()), v.end());
        built = true;
    }

    int get_idx(T x) {
        assert(built);
        return lower_bound(v.begin(), v.end(), x) - v.begin();
    }

    T &operator[](int i) {
        assert(built);
        return v[i];
    }

   private:
    std::vector<T> v;
    bool built;
};

}  // namespace rklib


#include <algorithm>
#include <cassert>
#include <vector>

namespace rklib {

template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
bool chmin_non_negative(T &a, const T &b) {
    if (a < 0 || a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
T div_floor(T num, T den) {
    if (den < 0) num = -num, den = -den;
    return num >= 0 ? num / den : (num + 1) / den - 1;
}

template <class T>
T div_ceil(T num, T den) {
    if (den < 0) num = -num, den = -den;
    return num <= 0 ? num / den : (num - 1) / den + 1;
}

}  // namespace rklib


using namespace std;
using namespace rklib;

using lint = long long;
using pii = pair<int, int>;
using pll = pair<lint, lint>;

struct Monoid {
    lint sum, sum_max, lsum_max, rsum_max;

    static Monoid op(Monoid a, Monoid b) {
        if (a.sum == LLONG_MAX) return b;
        if (b.sum == LLONG_MAX) return a;
        Monoid res;
        res.sum = a.sum + b.sum;
        res.sum_max = max({a.sum_max, b.sum_max, a.rsum_max + b.lsum_max});
        res.lsum_max = max(a.lsum_max, a.sum + b.lsum_max);
        res.rsum_max = max(a.rsum_max + b.sum, b.rsum_max);
        return res;
    }

    static Monoid e() { return {LLONG_MAX, 0, 0, 0}; }
};

int main() {
    int n;
    scanf("%d", &n);
    vector<pll> as;  // pos, val
    CoordComp<lint> xcmp;
    {
        lint l = 0;
        xcmp.add(l);
        rep(i, n) {
            lint a, b;
            scanf("%lld%lld", &a, &b);
            as.emplace_back(l, a);
            l += b;
            xcmp.add(l);
        }
        as.emplace_back(l, 0);
    }
    vector<tuple<int, lint, lint>> qs;
    int q;
    scanf("%d", &q);
    rep(i, q) {
        int c;
        lint x, y;
        scanf("%d%lld%lld", &c, &x, &y);
        --x;
        qs.emplace_back(c, x, y);

        xcmp.add(x);
        if (c == 2) xcmp.add(y);
    }

    xcmp.build();
    lint w[xcmp.size()];
    rep(i, xcmp.size()) {
        auto x = xcmp[i];
        auto it = prev(upper_bound(as.begin(), as.end(), pll(x, LLONG_MAX)));
        w[i] = it->se;
    }

    vector<Monoid> init(xcmp.size());
    rep(i, xcmp.size() - 1) {
        lint sum, sum_max, lsum_max, rsum_max;

        sum = w[i] * (xcmp[i + 1] - xcmp[i]);
        sum_max = lsum_max = rsum_max = (w[i] >= 0 ? sum : w[i]);

        init[i] = {sum, sum_max, lsum_max, rsum_max};
    }
    atcoder::segtree<Monoid, Monoid::op, Monoid::e> st(init);

    for (auto [c, x, y] : qs) {
        if (c == 1) {
            int pos = xcmp.get_idx(x);
            st.set(pos, {y, y, y, y});
        } else {
            int l = xcmp.get_idx(x), r = xcmp.get_idx(y);
            auto ans = st.prod(l, r);
            printf("%lld\n", ans.sum_max);
        }
    }
}
0