結果
問題 | No.865 24時間降水量 |
ユーザー |
![]() |
提出日時 | 2020-06-17 16:26:01 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 581 ms / 2,000 ms |
コード長 | 3,965 bytes |
コンパイル時間 | 1,574 ms |
コンパイル使用メモリ | 170,232 KB |
実行使用メモリ | 15,756 KB |
最終ジャッジ日時 | 2024-07-03 12:20:32 |
合計ジャッジ時間 | 4,891 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
/*** @FileName a.cpp* @Author kanpurin* @Created 2020.06.17 16:25:55**/#include "bits/stdc++.h"using namespace std;typedef long long ll;template<typename Monoid>struct LazySegmentTree {private:using Func = std::function<Monoid(Monoid, Monoid)>;Func F = [](Monoid a, Monoid b) { return max(a, b); };Monoid UNITY = 0;int n;std::vector<Monoid> node, lazy;std::vector<int> prop;void eval(int k, int l, int r) {if (prop[k] != 0) {node[k] = lazy[k] + (prop[k] == 1 ? node[k] : 0);if (r - l > 1) {lazy[2 * k + 1] = lazy[k] + (prop[k] == 1 ? lazy[2 * k + 1] : 0);lazy[2 * k + 2] = lazy[k] + (prop[k] == 1 ? lazy[2 * k + 2] : 0);prop[2 * k + 1] = prop[2 * k + 2] = prop[k];}lazy[k] = 0;prop[k] = 0;}}public:LazySegmentTree(int m, Monoid val) {n = 1; while (n < m) n <<= 1;node.resize(n * 2 - 1, UNITY);lazy.resize(n * 2 - 1, 0);prop.resize(n * 2 - 1, 0);if (val != LazySegmentTree::UNITY) {for (int i = 0; i < m; i++) node[n + i - 1] = val;build();}}LazySegmentTree(const std::vector<Monoid>& v) {int sz = v.size();n = 1; while (n < sz) n <<= 1;node.resize(n * 2 - 1, UNITY);lazy.resize(n * 2 - 1, 0);prop.resize(n * 2 - 1, 0);for (int i = 0; i < sz; i++) node[i + n - 1] = v[i];build();}void set(int k, const Monoid &x) {node[n + k - 1] = x;}void build() {for (int i = n - 2; i >= 0; i--) node[i] = F(node[2 * i + 1], node[2 * i + 2]);}void add_query(int a, int b, const Monoid &x, int k = 0, int l = 0, int r = -1) {if (r < 0) r = n;eval(k, l, r);if (b <= l || r <= a) return;if (a <= l && r <= b) {prop[k] = 1;lazy[k] += x;eval(k, l, r);}else {add_query(a, b, x, 2 * k + 1, l, (r - l) / 2 + l);add_query(a, b, x, 2 * k + 2, (r - l) / 2 + l, r);node[k] = F(node[2 * k + 1], node[2 * k + 2]);}}void update_query(int a, int b, const Monoid &x, int k = 0, int l = 0, int r = -1) {if (r < 0) r = n;eval(k, l, r);if (b <= l || r <= a) return;if (a <= l && r <= b) {prop[k] = 2;lazy[k] = x;eval(k, l, r);}else {update_query(a, b, x, 2 * k + 1, l, (r - l) / 2 + l);update_query(a, b, x, 2 * k + 2, (r - l) / 2 + l, r);node[k] = F(node[2 * k + 1], node[2 * k + 2]);}}Monoid get_query(int a, int b, int k = 0, int l = 0, int r = -1) {if (r < 0) r = n;if (r <= a || b <= l) return UNITY;eval(k, l, r);if (a <= l && r <= b) return node[k];Monoid vl = get_query(a, b, 2 * k + 1, l, (r - l) / 2 + l);Monoid vr = get_query(a, b, 2 * k + 2, (r - l) / 2 + l, r);return F(vl, vr);}Monoid operator[](int x) {return get_query(x, x + 1);}void print() {for (int i = 0; i < n; i++) {std::cout << i << "\t: " << get_query(i, i + 1) << std::endl;}}};int main() {int n;cin >> n;vector<int> a(n);vector<ll> sum(n-23);for (int i = 0; i < n; i++) {cin >> a[i];if (i < 23) {sum[0] += a[i];}else {if (i != 23) sum[i-23] = sum[i-24] - a[i-24];sum[i-23] += a[i];}}LazySegmentTree<ll> seg(sum);int q;cin >> q;for (int i = 0; i < q; i++) {int t, v;cin >> t >> v;t--;seg.add_query(t-23,t+1,v-a[t]);a[t] = v;cout << seg.get_query(0,n) << endl;}return 0;}