結果

問題 No.2333 Slime Structure
ユーザー Ricky_ponRicky_pon
提出日時 2023-05-28 16:47:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,197 bytes
コンパイル時間 1,798 ms
コンパイル使用メモリ 148,632 KB
最終ジャッジ日時 2025-02-13 15:28:18
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:170:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  170 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
main.cpp:178:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  178 |             scanf("%lld%lld", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
main.cpp:187:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  187 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
main.cpp:191:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  191 |         scanf("%d%lld%lld", &c, &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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