結果
問題 | No.2333 Slime Structure |
ユーザー |
|
提出日時 | 2023-05-28 15:14:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 157 ms / 3,000 ms |
コード長 | 8,718 bytes |
コンパイル時間 | 1,974 ms |
コンパイル使用メモリ | 211,308 KB |
最終ジャッジ日時 | 2025-02-13 12:46:01 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < (n); i++)#define per(i, n) for (int i = (n)-1; i >= 0; i--)#define rep2(i, l, r) for (int i = (l); i < (r); i++)#define per2(i, l, r) for (int i = (r)-1; i >= (l); i--)#define each(e, v) for (auto &e : v)#define MM << " " <<#define pb push_back#define eb emplace_back#define all(x) begin(x), end(x)#define rall(x) rbegin(x), rend(x)#define sz(x) (int)x.size()using ll = long long;using pii = pair<int, int>;using pil = pair<int, ll>;using pli = pair<ll, int>;using pll = pair<ll, ll>;template <typename T>using minheap = priority_queue<T, vector<T>, greater<T>>;template <typename T>using maxheap = priority_queue<T>;template <typename T>bool chmax(T &x, const T &y) {return (x < y) ? (x = y, true) : false;}template <typename T>bool chmin(T &x, const T &y) {return (x > y) ? (x = y, true) : false;}template <typename T>int flg(T x, int i) {return (x >> i) & 1;}int popcount(int x) { return __builtin_popcount(x); }int popcount(ll x) { return __builtin_popcountll(x); }int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }int botbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }int botbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }template <typename T>void print(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');if (v.empty()) cout << '\n';}template <typename T>void printn(const vector<T> &v, T x = 0) {int n = v.size();for (int i = 0; i < n; i++) cout << v[i] + x << '\n';}template <typename T>int lb(const vector<T> &v, T x) {return lower_bound(begin(v), end(v), x) - begin(v);}template <typename T>int ub(const vector<T> &v, T x) {return upper_bound(begin(v), end(v), x) - begin(v);}template <typename T>void rearrange(vector<T> &v) {sort(begin(v), end(v));v.erase(unique(begin(v), end(v)), end(v));}template <typename T>vector<int> id_sort(const vector<T> &v, bool greater = false) {int n = v.size();vector<int> ret(n);iota(begin(ret), end(ret), 0);sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; });return ret;}template <typename T>void reorder(vector<T> &a, const vector<int> &ord) {int n = a.size();vector<T> b(n);for (int i = 0; i < n; i++) b[i] = a[ord[i]];swap(a, b);}template <typename T>T floor(T x, T y) {assert(y != 0);if (y < 0) x = -x, y = -y;return (x >= 0 ? x / y : (x - y + 1) / y);}template <typename T>T ceil(T x, T y) {assert(y != 0);if (y < 0) x = -x, y = -y;return (x >= 0 ? (x + y - 1) / y : x / y);}template <typename S, typename T>pair<S, T> operator+(const pair<S, T> &p, const pair<S, T> &q) {return make_pair(p.first + q.first, p.second + q.second);}template <typename S, typename T>pair<S, T> operator-(const pair<S, T> &p, const pair<S, T> &q) {return make_pair(p.first - q.first, p.second - q.second);}template <typename S, typename T>istream &operator>>(istream &is, pair<S, T> &p) {S a;T b;is >> a >> b;p = make_pair(a, b);return is;}template <typename S, typename T>ostream &operator<<(ostream &os, const pair<S, T> &p) {return os << p.first << ' ' << p.second;}struct io_setup {io_setup() {ios_base::sync_with_stdio(false);cin.tie(NULL);cout << fixed << setprecision(15);}} io_setup;constexpr int inf = (1 << 30) - 1;constexpr ll INF = (1LL << 60) - 1;// constexpr int MOD = 1000000007;constexpr int MOD = 998244353;template <typename Monoid>struct Segment_Tree {using M = typename Monoid::V;int n, m;vector<M> seg;// f(f(a,b),c) = f(a,f(b,c)), f(e1,a) = f(a,e1) = aSegment_Tree(const vector<M> &v) : n(v.size()) {m = 1;while (m < n) m <<= 1;seg.assign(2 * m, Monoid::id);copy(begin(v), end(v), begin(seg) + m);build();}Segment_Tree(int n, M x = Monoid::id) : Segment_Tree(vector<M>(n, x)) {}void set(int i, const M &x) { seg[m + i] = x; }void build() {for (int i = m - 1; i > 0; i--) seg[i] = Monoid::merge(seg[2 * i], seg[2 * i + 1]);}void update(int i, const M &x, bool apply = false) {seg[i + m] = apply ? Monoid::merge(seg[i + m], x) : x;i += m;while (i >>= 1) seg[i] = Monoid::merge(seg[2 * i], seg[2 * i + 1]);}M query(int l, int r) const {l = max(l, 0), r = min(r, n);M L = Monoid::id, R = Monoid::id;l += m, r += m;while (l < r) {if (l & 1) L = Monoid::merge(L, seg[l++]);if (r & 1) R = Monoid::merge(seg[--r], R);l >>= 1, r >>= 1;}return Monoid::merge(L, R);}M operator[](int i) const { return seg[m + i]; }template <typename C>int find_subtree(int i, const C &check, M &x, int type) const {while (i < m) {M nxt = type ? Monoid::merge(seg[2 * i + type], x) : Monoid::merge(x, seg[2 * i + type]);if (check(nxt)) {i = 2 * i + type;} else {x = nxt;i = 2 * i + (type ^ 1);}}return i - m;}// check(区間 [l,r] での演算結果) を満たす最小の r (存在しなければ n)template <typename C>int find_first(int l, const C &check) const {M L = Monoid::id;int a = l + m, b = 2 * m;while (a < b) {if (a & 1) {M nxt = Monoid::merge(L, seg[a]);if (check(nxt)) return find_subtree(a, check, L, 0);L = nxt;a++;}a >>= 1, b >>= 1;}return n;}// check((区間 [l,r) での演算結果)) を満たす最大の l (存在しなければ -1)template <typename C>int find_last(int r, const C &check) const {M R = Monoid::id;int a = m, b = r + m;while (a < b) {if ((b & 1) || a == 1) {M nxt = Monoid::merge(seg[--b], R);if (check(nxt)) return find_subtree(b, check, R, 1);R = nxt;}a >>= 1, b >>= 1;}return -1;}};struct Data_1 {ll l, r, ma, sum;constexpr Data_1() : l(-INF), r(-INF), ma(-INF), sum(0) {}Data_1(ll x, ll t) {if (x >= 0) {l = r = ma = x * t;sum = x * t;} else {l = r = ma = x;sum = x * t;}}};struct Monoid_1 {using V = Data_1;static V merge(V a, V b) {if (a.l == -INF) return b;if (b.l == -INF) return a;V c;c.l = max(a.l, a.sum + b.l);c.r = max(b.r, a.r + b.sum);c.sum = a.sum + b.sum;c.ma = max({a.ma, b.ma, a.r + b.l});return c;}static const V id;};constexpr Monoid_1::V Monoid_1::id = Data_1();struct Func_1 {constexpr Func_1() {}};struct Operator_1 {using V = Func_1;static V merge(V a, V b) { return a; }static const V id;};constexpr Operator_1::V Operator_1::id = Func_1();struct Acted_Monoid_1 {using Monoid = Monoid_1;using Operator = Operator_1;using M = typename Monoid::V;using O = typename Operator::V;static M merge(M a, O b) { return a; }};void solve() {int N;cin >> N;vector<ll> a(N), b(N);rep(i, N) cin >> a[i] >> b[i];vector<ll> xs;xs.eb(0);ll s = 0;rep(i, N) {s += b[i];xs.eb(s);}int Q;cin >> Q;vector<ll> t(Q), x(Q), y(Q);rep(i, Q) {cin >> t[i] >> x[i] >> y[i];if (t[i] == 1) {x[i]--;xs.eb(x[i]), xs.eb(x[i] + 1);} else {x[i]--;xs.eb(x[i]), xs.eb(y[i]);}}rearrange(xs);int K = sz(xs);Segment_Tree<Monoid_1> seg(K - 1);s = 0;int p = 0;rep(i, N) {while (xs[p] < s + b[i]) {seg.set(p, Data_1(a[i], xs[p + 1] - xs[p]));p++;}s += b[i];}seg.build();rep(i, Q) {if (t[i] == 1) {int t = lb(xs, x[i]);seg.update(t, Data_1(y[i], 1));} else {int L = lb(xs, x[i]), R = lb(xs, y[i]);cout << seg.query(L, R).ma << '\n';}}}int main() {int T = 1;// cin >> T;while (T--) solve();}