結果
問題 | No.776 A Simple RMQ Problem |
ユーザー | Haar |
提出日時 | 2019-10-17 12:12:27 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 465 ms / 3,000 ms |
コード長 | 4,291 bytes |
コンパイル時間 | 2,531 ms |
コンパイル使用メモリ | 210,720 KB |
実行使用メモリ | 12,272 KB |
最終ジャッジ日時 | 2024-06-24 01:33:32 |
合計ジャッジ時間 | 13,065 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 33 ms
5,632 KB |
testcase_03 | AC | 129 ms
12,048 KB |
testcase_04 | AC | 174 ms
5,504 KB |
testcase_05 | AC | 282 ms
12,152 KB |
testcase_06 | AC | 76 ms
7,616 KB |
testcase_07 | AC | 180 ms
12,104 KB |
testcase_08 | AC | 224 ms
7,600 KB |
testcase_09 | AC | 69 ms
12,160 KB |
testcase_10 | AC | 122 ms
7,680 KB |
testcase_11 | AC | 231 ms
12,160 KB |
testcase_12 | AC | 294 ms
12,160 KB |
testcase_13 | AC | 297 ms
12,160 KB |
testcase_14 | AC | 297 ms
12,272 KB |
testcase_15 | AC | 300 ms
12,160 KB |
testcase_16 | AC | 297 ms
12,240 KB |
testcase_17 | AC | 465 ms
12,160 KB |
testcase_18 | AC | 170 ms
12,160 KB |
testcase_19 | AC | 380 ms
12,160 KB |
testcase_20 | AC | 385 ms
12,260 KB |
testcase_21 | AC | 384 ms
12,228 KB |
testcase_22 | AC | 383 ms
12,172 KB |
testcase_23 | AC | 378 ms
12,160 KB |
testcase_24 | AC | 382 ms
12,160 KB |
testcase_25 | AC | 55 ms
5,376 KB |
testcase_26 | AC | 158 ms
12,160 KB |
testcase_27 | AC | 123 ms
12,160 KB |
ソースコード
#include <bits/stdc++.h> #define LLI long long int #define FOR(v, a, b) for(LLI v = (a); v < (b); ++v) #define FORE(v, a, b) for(LLI v = (a); v <= (b); ++v) #define REP(v, n) FOR(v, 0, n) #define REPE(v, n) FORE(v, 0, n) #define REV(v, a, b) for(LLI v = (a); v >= (b); --v) #define ALL(x) (x).begin(), (x).end() #define RALL(x) (x).rbegin(), (x).rend() #define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it) #define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it) #define EXIST(c,x) ((c).find(x) != (c).end()) #define fst first #define snd second #define popcount __builtin_popcount #define UNIQ(v) (v).erase(unique(ALL(v)), (v).end()) #define bit(i) (1LL<<(i)) #ifdef DEBUG #include <misc/C++/Debug.cpp> #else #define dump(...) ((void)0) #endif #define gcd __gcd using namespace std; template <class T> constexpr T lcm(T m, T n){return m/gcd(m,n)*n;} template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;} template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;} template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);} template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);} template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);} struct Init{ Init(){ cin.tie(0); ios::sync_with_stdio(false); } }init; template <typename Monoid> class SegmentTree{ private: int size; vector<Monoid> vec; inline Monoid aux(int x, int y, int i, int l, int r){ if(r<=x || y<=l) return Monoid::identity(); else if(x<=l && r<=y) return vec[i]; else return Monoid::op(aux(x,y,i*2+1,l,(l+r)/2), aux(x,y,i*2+2,(l+r)/2,r)); }; public: SegmentTree(int n){ size = 1; while(size < n) size *= 2; size = size*2-1; vec = vector<Monoid>(size, Monoid::identity()); } inline void update(int i, const Monoid &x){ int j = i+(size+1)/2-1; vec[j] = x; --j; while(j>=0){ vec[j/2] = Monoid::op(vec[(j/2)*2+1], vec[(j/2)*2+2]); (j /= 2) -= 1; } } inline Monoid at(int i){ return vec[(size+1)/2 + i - 1]; } inline Monoid get(int x, int y){ // [x,y) return aux(x,y,0,0,(size+1)/2); } }; template <typename T, T NEGINF> struct MaxPartialSumMonoid{ T sum, left_max, right_max, partial_max; using M = MaxPartialSumMonoid; static M op(const M &a, const M &b){ return MaxPartialSumMonoid({ a.sum + b.sum, max({a.left_max, a.sum+b.left_max, a.sum+b.sum}), max({b.right_max, b.sum+a.right_max, a.sum+b.sum}), max({a.partial_max, b.partial_max, a.right_max+b.left_max}) }); } static constexpr M identity(){ return MaxPartialSumMonoid({0, NEGINF, NEGINF, NEGINF}); } static constexpr M make(const T &a){ return MaxPartialSumMonoid({a, a, a, a}); } friend ostream& operator<<(ostream &os, const M &val){ os << val.sum << "," << val.left_max << "," << val.right_max << "," << val.partial_max; return os; } }; using M = MaxPartialSumMonoid<LLI,(-(1LL<<50))>; int main(){ int N,Q; while(cin >> N >> Q){ SegmentTree<M> seg(N); vector<LLI> a(N); cin >> a; REP(i,N){ seg.update(i, M::make(a[i])); } REP(i,Q){ string com; cin >> com; if(com == "set"){ int i, x; cin >> i >> x; --i; seg.update(i, M::make(x)); a[i] = x; }else{ int l1, l2, r1, r2; cin >> l1 >> l2 >> r1 >> r2; --l1, --l2, --r1, --r2; r1 = max(l1,r1); l2 = min(l2,r2); LLI ans = LLONG_MIN; if(l2 <= r1){ ans = seg.get(l1,l2+1).right_max + seg.get(l2,r1+1).sum + seg.get(r1,r2+1).left_max - a[r1] - a[l2]; }else{ chmax(ans, seg.get(l1,r1+1).right_max + seg.get(r1,r2+1).left_max - a[r1]); chmax(ans, seg.get(l1,l2+1).right_max + seg.get(l2,r2+1).left_max - a[l2]); chmax(ans, seg.get(r1,l2+1).partial_max); } cout << ans << endl; } } cerr << endl; } return 0; }