結果
問題 | No.776 A Simple RMQ Problem |
ユーザー | paruki |
提出日時 | 2019-01-24 22:02:15 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 491 ms / 3,000 ms |
コード長 | 5,056 bytes |
コンパイル時間 | 2,005 ms |
コンパイル使用メモリ | 183,780 KB |
実行使用メモリ | 17,668 KB |
最終ジャッジ日時 | 2024-09-16 04:44:07 |
合計ジャッジ時間 | 11,545 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 38 ms
6,656 KB |
testcase_03 | AC | 158 ms
16,128 KB |
testcase_04 | AC | 207 ms
7,040 KB |
testcase_05 | AC | 350 ms
16,512 KB |
testcase_06 | AC | 95 ms
9,464 KB |
testcase_07 | AC | 217 ms
16,768 KB |
testcase_08 | AC | 275 ms
9,600 KB |
testcase_09 | AC | 82 ms
17,152 KB |
testcase_10 | AC | 152 ms
9,984 KB |
testcase_11 | AC | 286 ms
17,368 KB |
testcase_12 | AC | 364 ms
17,660 KB |
testcase_13 | AC | 363 ms
17,664 KB |
testcase_14 | AC | 365 ms
17,572 KB |
testcase_15 | AC | 378 ms
17,556 KB |
testcase_16 | AC | 369 ms
17,668 KB |
testcase_17 | AC | 491 ms
17,536 KB |
testcase_18 | AC | 282 ms
17,664 KB |
testcase_19 | AC | 435 ms
17,648 KB |
testcase_20 | AC | 432 ms
17,664 KB |
testcase_21 | AC | 426 ms
17,652 KB |
testcase_22 | AC | 431 ms
17,664 KB |
testcase_23 | AC | 427 ms
17,664 KB |
testcase_24 | AC | 427 ms
17,648 KB |
testcase_25 | AC | 57 ms
5,376 KB |
testcase_26 | AC | 277 ms
17,632 KB |
testcase_27 | AC | 238 ms
17,656 KB |
ソースコード
#define _USE_MATH_DEFINES #include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define MT make_tuple #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)<<endl #define smax(x,y) (x)=max((x),(y)) #define smin(x,y) (x)=min((x),(y)) #define MEM(x,y) memset((x),(y),sizeof (x)) #define sz(x) (int)(x).size() #define RT return using ll = long long; using pii = pair<int, int>; using vi = vector<int>; using vll = vector<ll>; template<class P, class Q> struct LazySegTree { int dataSize; vector<P> value; vector<Q> lazy; function<P(P, P)> f; function<P(P, Q)> g; function<Q(Q, Q)> h; LazySegTree(vector<P> dat, function<P(P, P)> f_, function<P(P, Q)> g_, function<Q(Q, Q)> h_){ f = f_; g = g_; h = h_; dataSize = 1; int n = (int)dat.size(); while (dataSize < n)dataSize *= 2; int treeSize = 2 * dataSize; value = vector<P>(treeSize, P()); lazy = vector<Q>(treeSize, Q()); for (int i = 0; i < n; ++i) { value[dataSize + i] = dat[i]; } for (int i = dataSize - 1; i >= 0; --i) { value[i] = f(value[i * 2], value[i * 2 + 1]); } } void propagate(int index, int curL, int curR) { if (lazy[index] != Q()) { int left = index * 2, right = index * 2 + 1; value[index] = g(value[index], lazy[index]); if (curR - curL > 1) { lazy[left] = h(lazy[left], lazy[index]); lazy[right] = h(lazy[right], lazy[index]); } lazy[index] = Q(); } } void update(int index, int curL, int curR, int givenL, int givenR, Q x) { propagate(index, curL, curR); if (curR <= givenL || givenR <= curL)return; if (givenL <= curL && curR <= givenR) { lazy[index] = h(lazy[index], x); propagate(index, curL, curR); } else { int mid = (curL + curR) / 2; update(index * 2, curL, mid, givenL, givenR, x); update(index * 2 + 1, mid, curR, givenL, givenR, x); value[index] = f(value[index * 2], value[index * 2 + 1]); } } void update(int l, int r, Q x) { update(1, 0, dataSize, l, r, x); } P query(int l, int r) { return query(1, 0, dataSize, l, r); } P query(int index, int curL, int curR, int givenL, int givenR) { if (curR <= givenL || givenR <= curL)return P(); propagate(index, curL, curR); if (givenL <= curL && curR <= givenR) { return value[index]; } else { int mid = (curL + curR) / 2; P resL = query(index * 2, curL, mid, givenL, givenR); P resR = query(index * 2 + 1, mid, curR, givenL, givenR); return f(resL, resR); } } }; struct P { ll mi, ma, mm; P() { mi = LLONG_MAX / 3; ma = LLONG_MIN / 3; mm = LLONG_MIN / 3; } P(ll a, ll b, ll c):mi(a),ma(b),mm(c){} }; P f(P l, P r) { return P(min(l.mi, r.mi), max(l.ma, r.ma), max(r.ma - l.mi, max(l.mm, r.mm))); } P g(P p, ll q) { p.mi += q; p.ma += q; return p; } void solve() { int N, Q; cin >> N >> Q; vll a(N), sm(N + 1); rep(i, N) { cin >> a[i]; sm[i + 1] = sm[i] + a[i]; } vector<P> ps(N + 1); rep(i, N + 1)ps[i] = P(sm[i], sm[i], LLONG_MIN/3); LazySegTree<P, ll> lst(ps, f, g, plus<ll>()); rep(hoge, Q) { string s; cin >> s; if (s == "max") { int L1, L2, R1, R2; cin >> L1 >> L2 >> R1 >> R2; ll ans = LLONG_MIN; if (L2 <= R1) { ans = lst.query(R1, R2 + 1).ma - lst.query(L1 - 1, L2).mi; } else if (L1 <= R1 && R2 <= L2) { smax(ans, lst.query(R1, R2 + 1).ma - lst.query(L1 - 1, R1).mi); smax(ans, lst.query(R1 - 1, R2 + 1).mm); } else if (R1 <= L1 && L2 <= R2) { smax(ans, lst.query(L2, R2 + 1).ma - lst.query(L1 - 1, L2).mi); smax(ans, lst.query(L1 - 1, L2 + 1).mm); } else if (R1 <= L1) { ans = lst.query(L1 - 1, R2 + 1).mm; }else { if (L2 <= R2) { smax(ans, lst.query(L2, R2 + 1).ma - lst.query(L1 - 1, L2).mi); } if (L1 <= R1) { smax(ans, lst.query(R1, R2 + 1).ma - lst.query(L1 - 1, R1).mi); } smax(ans, lst.query(R1 - 1, L2 + 1).mm); } cout << ans << endl; } else { int i, x; cin >> i >> x; ll d = x - a[i - 1]; lst.update(i, N + 1, d); a[i - 1] = x; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15); solve(); return 0; }