結果
| 問題 | No.2333 Slime Structure |
| ユーザー |
 Ricky_pon
|
| 提出日時 | 2023-05-28 15:53:53 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,358 bytes |
| コンパイル時間 | 1,743 ms |
| コンパイル使用メモリ | 154,596 KB |
| 実行使用メモリ | 55,568 KB |
| 最終ジャッジ日時 | 2024-06-08 08:48:55 |
| 合計ジャッジ時間 | 10,213 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| 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 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| 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 | - |
ソースコード
#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(LLONG_MAX / 10, 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;
}
rep(i, xcmp.size()) printf("%lld %lld\n", xcmp[i], w[i]);
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);
}
// rep(i, xcmp.size()) printf("%lld ", st.get(i).sum_max);
// puts("");
}
}