結果
問題 | No.865 24時間降水量 |
ユーザー | noisy_noimin |
提出日時 | 2019-08-16 22:09:38 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,477 bytes |
コンパイル時間 | 1,144 ms |
コンパイル使用メモリ | 102,064 KB |
実行使用メモリ | 13,168 KB |
最終ジャッジ日時 | 2024-09-22 17:00:29 |
合計ジャッジ時間 | 4,330 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | WA | - |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | AC | 2 ms
6,944 KB |
testcase_19 | AC | 2 ms
6,944 KB |
testcase_20 | AC | 2 ms
6,944 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>; constexpr ll MOD = 1000000007; constexpr long double EPS = 1e-10; constexpr int dyx[4][2] = { { 0, 1}, {-1, 0}, {0,-1}, {1, 0} }; constexpr int MAX_N = 200000; template<typename T> class LazyRMQ { public: int n; T inf = INT_MAX; vector<T> data, lazy; LazyRMQ(int m, T init_value=0){ // 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] = max(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 max(vl, vr); } T find(int s, int t) { return find(s, t, 0, 0, n); } }; int main() { int n; cin >> n; vector<ll> a(n+1); LazyRMQ<ll> tree(n+3); // [t-23, t] の和 for(int i=1;i<=n;++i){ cin >> a[i]; tree.add(i, min(n+1, i+24), a[i]); } int q, t; ll v; cin >> q; for(int i=0;i<q;++i){ cin >> t >> v; ll v_diff = v - a[t]; tree.add(t, min(t+24, n+1), v_diff); cout << tree.find(24, n+1) << endl; } }