結果
問題 | No.2333 Slime Structure |
ユーザー |
![]() |
提出日時 | 2023-05-09 02:08:51 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 435 ms / 3,000 ms |
コード長 | 3,021 bytes |
コンパイル時間 | 5,208 ms |
コンパイル使用メモリ | 322,240 KB |
実行使用メモリ | 108,616 KB |
最終ジャッジ日時 | 2024-11-25 16:11:11 |
合計ジャッジ時間 | 20,999 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/all>using namespace atcoder;using ll = long long;using ld = long double;using P = pair<int, int>;using Graph = vector<vector<ll>>;using vi = vector<int>;using vl = vector<long>;using vll = vector<long long>;using vvi = vector<vi>;using vvl = vector<vl>;using vvll = vector<vll>;using vs = vector<string>;using vc = vector<char>;using vvc = vector<vc>;using pll = pair<long long, long long>;using vpll = vector<pll>;using mint = modint1000000007;const long double EPS = 1e-18;const long long INF = 1e15;const long double PI = acos(-1.0L);#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)#define repd(i, n) for (ll i = n - 1; i >= 0; i--)#define rrepd(i, n) for (ll i = n; i >= 1; i--)#define ALL(n) begin(n), end(n)#define IN(a, x, b) (a <= x && x < b)#define INIT \std::ios::sync_with_stdio(false); \std::cin.tie(0);template <class T>inline T CHMAX(T& a, const T b) {return a = (a < b) ? b : a;}template <class T>inline T CHMIN(T& a, const T b) {return a = (a > b) ? b : a;}struct S {ll left_max;ll right_max;ll kukan_max;ll sum;};S op(S a, S b) {return S{max(a.left_max, a.sum + b.left_max),max(b.right_max, b.sum + a.right_max),max(max(a.kukan_max, b.kukan_max), a.right_max + b.left_max),a.sum + b.sum};}S e() { return S{-INF, -INF, -INF, 0ll}; }int main() {INIT;ll N;cin >> N;vll A(1e5 + 100), B(1e5 + 100);rrep(i, N) { cin >> A[i] >> B[i]; }ll Q;cin >> Q;vll q(1e5 + 100), a(1e5 + 100), b(1e5 + 100);vll num;num.push_back(0ll);rrep(i, N) { num.push_back(num[i - 1] + B[i]); }vll numnum = num;rrep(i, N) {num.push_back(numnum[i] - 1);num.push_back(numnum[i] + 1);}rrep(i, Q) {cin >> q[i] >> a[i] >> b[i];num.push_back(a[i] - 1);num.push_back(a[i]);num.push_back(a[i] + 1);if (q[i] == 2) {num.push_back(b[i] - 1);num.push_back(b[i]);num.push_back(b[i] + 1);}}sort(ALL(num));num.erase(unique(ALL(num)), num.end());ll su = num.size();segtree<S, op, e> seg(su + 1);rrep(i, num.size() - 1) {auto itr = lower_bound(ALL(numnum), num[i]);ll l = itr - numnum.begin();ll haba = num[i] - num[i - 1];seg.set(i, S{A[l] * haba, A[l] * haba, A[l] * haba, A[l] * haba});}rrep(i, Q) {if (q[i] == 1) {ll l = lower_bound(ALL(num), a[i]) - num.begin();seg.set(l, S{b[i], b[i], b[i], b[i]});} else {ll l = lower_bound(ALL(num), a[i]) - num.begin();ll r = lower_bound(ALL(num), b[i]) - num.begin();cout << seg.prod(l, r + 1).kukan_max << endl;}}}