結果
問題 | No.2333 Slime Structure |
ユーザー |
|
提出日時 | 2023-05-05 19:38:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 371 ms / 3,000 ms |
コード長 | 4,229 bytes |
コンパイル時間 | 2,198 ms |
コンパイル使用メモリ | 217,784 KB |
最終ジャッジ日時 | 2025-02-12 17:20:03 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename X>struct SegTree{using FX = function<X(X, X)>; // X•X -> X となる関数の型int n;FX fx;const X ex;vector<X> dat;SegTree(int n_, FX fx_, X ex_) : n(), fx(fx_), ex(ex_){int x = 1;while(n_ > x){x *= 2;}n = x;dat.assign(n * 2, ex);}X get(int i){return dat[i + n];}void set(int i, X x){ dat[i + n] = x; }void build(){for(int k = n - 1; k >= 1; k--) dat[k] = fx(dat[k * 2], dat[k * 2 + 1]);}void update(int i, X x){i += n;dat[i] = x;while(i > 0){i >>= 1; // parentdat[i] = fx(dat[i * 2], dat[i * 2 + 1]);}}X query(int a, int b){X vl = ex;X vr = ex;int l = a + n;int r = b + n;while(l < r){if(l & 1) vl = fx(vl, dat[l++]);if(r & 1) vr = fx(dat[--r], vr);l >>= 1;r >>= 1;}return fx(vl, vr);}};const long long INF = 1LL << 40;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n, q; cin >> n;vector<long long> a(n), b(n);for(int i = 0; i < n; i++){cin >> a[i] >> b[i];}vector<long long> sum(n + 1), sum2(n + 1);for(int i = 0; i < n; i++){sum[i + 1] = sum[i] + b[i];}sum2 = sum;cin >> q;vector<tuple<int, long long, long long>> query(q);vector<int> check;for(int i = 0; i < q; i++){int t;long long x, y; cin >> t >> x >> y;query[i] = {t, x, y};if(t == 1){sum2.push_back(x - 1);sum2.push_back(x);}}sort(sum2.begin(), sum2.end());sum2.erase(unique(sum2.begin(), sum2.end()), sum2.end());using T = tuple<long long, long long, long long, long long>;auto fx = [](T x, T y) -> T {auto [all1, left1, right1, res1] = x;auto [all2, left2, right2, res2] = y;return {all1 + all2, max(left1, all1 + left2), max(right2, all2 + right1), max({res1, res2, right1 + left2})};};int m = sum2.size() - 1;SegTree<T> seg(m, fx, T(0, -INF, -INF, -INF));for(int i = 1; i <= m; i++){auto iter = lower_bound(sum.begin(), sum.end(), sum2[i]);int k = (iter - sum.begin()) - 1;int siz = sum2[i] - sum2[i - 1];if(a[k] < 0){seg.update(i - 1, T(a[k] * siz, a[k], a[k], a[k]));}else{seg.update(i - 1, T(a[k] * siz, a[k] * siz, a[k] * siz, a[k] * siz));}}for(int i = 0; i < q; i++){auto [t, x, y] = query[i];if(t == 1){x--;int k = upper_bound(sum2.begin(), sum2.end(), x) - sum2.begin(); k--;seg.update(k, T(y, y, y, y));}else{x--;int k1 = upper_bound(sum2.begin(), sum2.end(), x) - sum2.begin(); k1--;int k2 = upper_bound(sum2.begin(), sum2.end(), y - 1) - sum2.begin(); k2--;if(k1 == k2){int v = get<0>(seg.get(k1)) / (sum2[k1 + 1] - sum2[k1]);if(v < 0){cout << v << endl;}else{cout << v * (y - x) << endl;}}else{int l = k1 + 1, r = k2;T left, right;long long v1 = get<0>(seg.get(k1)) / (sum2[k1 + 1] - sum2[k1]);long long s1 = v1 * (sum2[k1 + 1] - x);if(v1 < 0){left = T(s1, v1, v1, v1);}else{left = T(s1, s1, s1, s1);}long long v2 = get<0>(seg.get(k2)) / (sum2[k2 + 1] - sum2[k2]);long long s2 = v2 * (y - sum2[k2]);if(v2 < 0){right = T(s2, v2, v2, v2);}else{right = T(s2, s2, s2, s2);}T ans = left;ans = fx(ans, seg.query(l, r));ans = fx(ans, right);cout << get<3>(ans) << endl;}}}}