結果
問題 | No.865 24時間降水量 |
ユーザー | noisy_noimin |
提出日時 | 2019-08-16 22:45:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 627 ms / 2,000 ms |
コード長 | 2,574 bytes |
コンパイル時間 | 928 ms |
コンパイル使用メモリ | 101,596 KB |
実行使用メモリ | 8,192 KB |
最終ジャッジ日時 | 2024-09-22 19:10:44 |
合計ジャッジ時間 | 4,058 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 5 ms
5,376 KB |
testcase_06 | AC | 5 ms
5,376 KB |
testcase_07 | AC | 4 ms
5,376 KB |
testcase_08 | AC | 5 ms
5,376 KB |
testcase_09 | AC | 4 ms
5,376 KB |
testcase_10 | AC | 24 ms
5,376 KB |
testcase_11 | AC | 24 ms
5,376 KB |
testcase_12 | AC | 24 ms
5,376 KB |
testcase_13 | AC | 24 ms
5,376 KB |
testcase_14 | AC | 25 ms
5,376 KB |
testcase_15 | AC | 623 ms
8,192 KB |
testcase_16 | AC | 603 ms
8,064 KB |
testcase_17 | AC | 627 ms
8,064 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 2 ms
5,376 KB |
ソースコード
#include <cstdio>#include <cstdlib>#include <cmath>#include <climits>#include <cassert>#include <cstdint>#include <iostream>#include <iomanip>#include <string>#include <stack>#include <queue>#include <vector>#include <map>#include <set>#include <algorithm>#include <numeric>#include <bitset>using namespace std;using ll = long long;using Pll = pair<ll, ll>;using Pii = pair<int, int>;template<typename T> class LazyRMQ {public:int n;T inf = INT_MAX;vector<T> data, lazy;LazyRMQ(int m, T init_value=INT_MAX){// 2のべき乗にするn = 1;while(n < m) n <<= 1;data.assign(2*n-1, init_value);lazy.assign(2*n-1, 0);inf = init_value;}void eval(int k, int kl, int kr){if(data[k] == inf) data[k] = 0;if(lazy[k] == 0) return;data[k] += lazy[k];if(kr - kl > 1){lazy[2*k+1] += lazy[k];lazy[2*k+2] += lazy[k];}lazy[k] = 0;}// [s,t)void add(int s, int t, T x, int k, int kl, int kr){eval(k, kl, kr);if(kr <= s || t <= kl) return;if(s <= kl && kr <= t){lazy[k] += x;eval(k, kl, kr);return;}int kc = (kl+kr)/2;add(s, t, x, 2*k+1, kl, kc);add(s, t, x, 2*k+2, kc, kr);data[k] = min(data[2*k+1], data[2*k+2]);}void add(int s, int t, T x) {add(s, t, x, 0, 0, n);}// [s,t)T find(int s, int t, int k, int kl, int kr){eval(k, kl, kr);if(kr <= s || t <= kl) return inf;if(s <= kl && kr <= t) return data[k];int kc = (kl+kr)/2;T vl = find(s, t, 2*k+1, kl, kc);T vr = find(s, t, 2*k+2, kc, kr);return min(vl, vr);}T find(int s, int t) {return find(s, t, 0, 0, n);}};int main() {int n;cin >> n;vector<int> a(n+1);LazyRMQ<int> tree(n-20); // [t, t+24) の和for(int i=1;i<=n;++i){cin >> a[i];tree.add(max(1, i-23), i+1, -a[i]);}// for(int i=1;i<=n;++i) {// cerr << tree.find(i, i+1) << " ";// }// cerr << endl;int q, t;int v;cin >> q;for(int i=0;i<q;++i){cin >> t >> v;int v_diff = v - a[t];tree.add(max(1, t-23), t+1, -v_diff);cout << -tree.find(0, n-20) << endl;// for(int i=1;i<=n;++i) {// cerr << tree.find(i, i+1) << " ";// }// cerr << endl;a[t] = v;}}