結果
問題 | No.865 24時間降水量 |
ユーザー |
![]() |
提出日時 | 2019-08-17 05:03:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 220 ms / 2,000 ms |
コード長 | 4,841 bytes |
コンパイル時間 | 1,273 ms |
コンパイル使用メモリ | 109,596 KB |
実行使用メモリ | 7,884 KB |
最終ジャッジ日時 | 2024-09-24 18:42:03 |
合計ジャッジ時間 | 3,380 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
// includes {{{#include<iostream>#include<iomanip>#include<algorithm>#include<vector>#include<stack>#include<queue>#include<map>#include<set>#include<tuple>#include<cmath>#include<random>#include<cassert>#include<bitset>#include<cstdlib>// #include<deque>// #include<multiset>// #include<cstring>// #include<bits/stdc++.h>// }}}using namespace std;using ll = long long;// SegmentTree( size [, initial] )// SegmentTree( <data> )/// --- SegmentTree {{{ ///#include <cassert>#include <initializer_list>#include <iostream>#include <iterator>#include <vector>template < class Monoid >struct SegmentTree {private:using T = typename Monoid::T;using size_type = std::size_t;size_type n;std::vector< T > data;// call after touch data[i]void prop(int i) { data[i] = Monoid::op(data[2 * i], data[2 * i + 1]); }public:SegmentTree() : n(0) {}SegmentTree(int n, T initial = Monoid::identity()) : n(n) {data.resize(n * 2, initial);for(int i = n - 1; i > 0; i--) data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]);}template < class InputIter,class = typename std::iterator_traits< InputIter >::value_type >SegmentTree(InputIter first, InputIter last) : SegmentTree(distance(first, last)) {copy(first, last, data.begin() + n);// fill from deepfor(int i = n - 1; i > 0; i--) prop(i);}SegmentTree(std::vector< T > v) : SegmentTree(v.begin(), v.end()) {}SegmentTree(std::initializer_list< T > v) : SegmentTree(v.begin(), v.end()) {}void set(size_t i, const T &v) {assert(i < n);data[i += n] = v;while(i >>= 1) prop(i); // propUp}T get(size_t i) {assert(i < n);return data[i + n];}T fold(int l, int r) {if(l < 0) l = 0;if(l >= r) return Monoid::identity();if(r > static_cast< int >(n)) r = n;T tmpL = Monoid::identity(), tmpR = Monoid::identity();for(l += n, r += n; l < r; l >>= 1, r >>= 1) {if(l & 1) tmpL = Monoid::op(tmpL, data[l++]);if(r & 1) tmpR = Monoid::op(data[--r], tmpR);}return Monoid::op(tmpL, tmpR);}size_type size() { return n; }inline void dum(int r = -1) {#ifdef DEBUGif(r < 0) r = n;DEBUG_OUT << "{";for(int i = 0; i < std::min< int >(r, n); i++) DEBUG_OUT << (i ? ", " : "") << get(i);DEBUG_OUT << "}" << std::endl;#endif}};/// }}}--- ////// --- Monoid examples {{{ ///constexpr long long inf_monoid = 1e18 + 100;#include <algorithm>struct Nothing {using T = char;using Monoid = Nothing;using M = T;static constexpr T op(const T &, const T &) { return T(); }static constexpr T identity() { return T(); }template < class X >static constexpr X actInto(const M &, long long, const X &x) {return x;}};template < class U = long long >struct RangeMin {using T = U;static T op(const T &a, const T &b) { return std::min< T >(a, b); }static constexpr T identity() { return T(inf_monoid); }};template < class U = long long >struct RangeMax {using T = U;static T op(const T &a, const T &b) { return std::max< T >(a, b); }static constexpr T identity() { return T(-inf_monoid); }};template < class U = long long >struct RangeSum {using T = U;static T op(const T &a, const T &b) { return a + b; }static constexpr T identity() { return T(0); }};template < class U >struct RangeProd {using T = U;static T op(const T &a, const T &b) { return a * b; }static constexpr T identity() { return T(1); }};template < class U = long long >struct RangeOr {using T = U;static T op(const T &a, const T &b) { return a | b; }static constexpr T identity() { return T(0); }};#include <bitset>template < class U = long long >struct RangeAnd {using T = U;static T op(const T &a, const T &b) { return a & b; }static constexpr T identity() { return T(-1); }};template < size_t N >struct RangeAnd< std::bitset< N > > {using T = std::bitset< N >;static T op(const T &a, const T &b) { return a & b; }static constexpr T identity() { return std::bitset< N >().set(); }};/// }}}--- ///using Seg = SegmentTree< RangeMax<> >;// BIT使えみたいな見た目してるな,しらんがint main() {std::ios::sync_with_stdio(false), std::cin.tie(0);int n;cin >> n;vector<int> a(n + 100);for(int i = 0; i < n; i++) cin >> a[i + 50];vector<int> b(n + 100);for(int i = 0; i < n; i++) for(int j = 0; j < 24; j++) b[i + 50] += a[i + 50 + j];Seg seg(begin(b), end(b));int q;cin >> q;for(int i = 0; i < q; i++) {int t, v;cin >> t >> v;t--;for(int j = 0; j < 24; j++) seg.set(t + 50 - j, seg.get(t + 50 - j) + v - a[t + 50]);a[t + 50] = v;cout << seg.fold(50, 50 + n) << "\n";}return 0;}