結果
問題 | No.865 24時間降水量 |
ユーザー | Mayimg |
提出日時 | 2019-08-16 23:19:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 475 ms / 2,000 ms |
コード長 | 4,613 bytes |
コンパイル時間 | 2,830 ms |
コンパイル使用メモリ | 204,028 KB |
最終ジャッジ日時 | 2025-01-07 12:50:51 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,824 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 3 ms
6,820 KB |
testcase_04 | AC | 2 ms
6,816 KB |
testcase_05 | AC | 4 ms
6,820 KB |
testcase_06 | AC | 4 ms
6,820 KB |
testcase_07 | AC | 3 ms
6,824 KB |
testcase_08 | AC | 4 ms
6,816 KB |
testcase_09 | AC | 4 ms
6,816 KB |
testcase_10 | AC | 15 ms
6,816 KB |
testcase_11 | AC | 15 ms
6,820 KB |
testcase_12 | AC | 16 ms
6,820 KB |
testcase_13 | AC | 17 ms
6,816 KB |
testcase_14 | AC | 15 ms
6,820 KB |
testcase_15 | AC | 475 ms
6,816 KB |
testcase_16 | AC | 475 ms
6,820 KB |
testcase_17 | AC | 474 ms
6,820 KB |
testcase_18 | AC | 3 ms
6,820 KB |
testcase_19 | AC | 2 ms
6,816 KB |
testcase_20 | AC | 3 ms
6,820 KB |
ソースコード
#define _USE_MATH_DEFINES#include <bits/stdc++.h>using namespace std;template<typename Monoid> class SegmentTree {private:using Func = function<Monoid(Monoid, Monoid)>;Func func;Monoid unity;int siz;vector<Monoid> data;int n;int height;inline void build() {siz = 1;while (siz < n) siz <<= 1, ++height;data.assign(siz << 1, unity);for (int i = 0; i < n; i++) set(i, unity);for (int idx = siz - 1; idx > 0; idx--) data[idx] = func(data[(idx << 1) | 0], data[(idx << 1) | 1]);}template<typename T> inline void build(const T& arr) {if (!~n) n = (int) arr.size();siz = 1;while (siz < n) siz <<= 1, ++height;data.assign(siz << 1, unity);for (int i = 0; i < n; i++) set(i, arr[i]);for (int idx = siz - 1; idx > 0; idx--) data[idx] = func(data[(idx << 1) | 0], data[(idx << 1) | 1]);}inline void set(int idx, const Monoid& val) { assert(idx + siz < (int) data.size()); data[idx + siz] = val;}public:SegmentTree() {}SegmentTree (const Func f, const Monoid& u, const int& n_) : func(f), unity(u), n(n_) { build(); }template<typename T> SegmentTree (const T& arr, const Func f, const Monoid& u, int n_ = -1) : func(f), unity(u), n(n_) { build(arr); }void initialize (const Func f, const Monoid &u, const int& n_) { func = f; unity = u; n = n_; build(); }template<typename T> void initialize (const T& arr, const Func f, const Monoid& u, int n_ = -1) { func = f; unity = u; n = n_; buld(arr); }void modify (int idx, const Monoid& val) {idx += siz;data[idx] = val;while (idx >>= 1) data[idx] = func(data[(idx << 1) | 0], data[(idx << 1) | 1]);}//[left, right)Monoid get (int left, int right) {if (left > right) swap(left, right);Monoid val_left = unity, val_right = unity;for (int l = left + siz, r = right + siz; l < r; l >>= 1, r >>= 1) {if (l & 1) val_left = func(val_left, data[l++]);if (r & 1) val_right = func(data[--r], val_right);}return func(val_left, val_right);}template<typename U>int find (int start, int left, int right, int cur, Monoid& val, const U& f) {if (left + 1 == right) {val = func(val, data[cur]);return f(val) ? cur - siz : -1;}int mid = (left + right) >> 1;if (mid <= start) return find(start, mid, right, (cur << 1) | 1, val, f);if (start <= left && !f(func(val, data[cur]))) {val = func(val, data[cur]);return -1;}int val_left = find(start, left, mid, (cur << 1) | 0, val, f);if (~val_left) return val_left;return find(start, mid, right, (cur << 1) | 1, val, f);}template<typename U>int find (int start, const U& f) {Monoid val = unity;return find(start, 0, siz, 1, val, f);}inline Monoid operator[] (int idx) { return data[idx + siz]; }void print() {for (int i = 0; i < siz; i++) {cout << (*this)[i];if (i != siz - 1) cout << ", ";}cout << '\n';}};// long long maxfunction<long long(long long, long long)> LLMAX = [] (long long a, long long b) -> long long { return max(a, b); };const long long LLMAX_UNITY = numeric_limits<long long>::min();// int maxfunction<int(int, int)> INTMAX = [] (int a, int b) -> int { return max(a, b); };const int INTMAX_UNITY = numeric_limits<int>::min();// long long minfunction<long long(long long, long long)> LLMIN = [] (long long a, long long b) -> long long { return min(a, b); };const long long LLMIN_UNITY = numeric_limits<long long>::max();// int minfunction<int(int, int)> INTMIN = [] (int a, int b) -> int { return min(a, b); };const int INTMIN_UNITY = numeric_limits<int>::max();// long long sumfunction<long long(long long, long long)> LLSUM = [] (long long a, long long b) -> long long { return a + b; };const long long LLSUM_UNITY = 0LL;// int sumfunction<int(int, int)> INTSUM = [] (int a, int b) -> int { return a + b; };const int INTSUM_UNITY = 0;signed main() {ios::sync_with_stdio(false); cin.tie(0);int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}SegmentTree<int> sgt(INTMAX, INTMAX_UNITY, n + 10);for (int i = 0; i <= n - 24; i++) {int sum = 0;for (int j = 0; j < 24; j++) sum += a[i + j];sgt.modify(i, sum);}int q;cin >> q;while (q--) {int t, v;cin >> t >> v;t--;a[t] = v;for (int i = max(0, t - 24); i <= min(t, n - 24); i++) {int sum = 0;for (int j = 0; j < 24; j++) sum += a[i + j];sgt.modify(i, sum);}cout << sgt.get(0, n + 1) << '\n';}return 0;}