結果
問題 | 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; } } }