結果
問題 | No.865 24時間降水量 |
ユーザー |
![]() |
提出日時 | 2019-08-19 14:14:40 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 137 ms / 2,000 ms |
コード長 | 2,291 bytes |
コンパイル時間 | 733 ms |
コンパイル使用メモリ | 91,592 KB |
実行使用メモリ | 8,196 KB |
最終ジャッジ日時 | 2024-10-04 07:19:23 |
合計ジャッジ時間 | 2,568 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:90:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 90 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:92:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 92 | for (int i = 0; i < n; i++) scanf("%d", as + i); | ~~~~~^~~~~~~~~~~~~~ main.cpp:107:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 107 | scanf("%d", &qn); | ~~~~~^~~~~~~~~~~ main.cpp:111:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 111 | scanf("%d%d", &ti, &vi); | ~~~~~^~~~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*-** 865.cc: No.865 24時間降水量 - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int D = 24;const int MAX_N = 200000;const int MAX_E2 = 1 << 19; // = 524288/* typedef */template <typename T, const int MAX_E2>struct SegTreeMax {int n, e2;T nodes[MAX_E2], dls[MAX_E2];SegTreeMax() {}void init(int _n) {n = _n;for (e2 = 1; e2 < n; e2 <<= 1);//fill(nodes, nodes + MAX_E2, 0);//fill(dls, dls + MAX_E2, 0);}T &get(int i) { return nodes[e2 - 1 + i]; }void set(int i, T v) { get(i) = v; }void setall() {for (int j = e2 - 2; j >= 0; j--)nodes[j] = max(nodes[j * 2 + 1], nodes[j * 2 + 2]);}void add_range(int r0, int r1, T v, int k, int i0, int i1) {if (r1 <= i0 || i1 <= r0) return;if (r0 <= i0 && i1 <= r1) {nodes[k] += v;dls[k] += v;return;}int k0 = k * 2 + 1, k1 = k0 + 1;if (dls[k]) {nodes[k0] += dls[k], dls[k0] += dls[k];nodes[k1] += dls[k], dls[k1] += dls[k];dls[k] = 0;}int im = (i0 + i1) / 2;add_range(r0, r1, v, k0, i0, im);add_range(r0, r1, v, k1, im, i1);nodes[k] = max(nodes[k0], nodes[k1]);}void add_range(int r0, int r1, T v) { add_range(r0, r1, v, 0, 0, e2); }};/* global variables */int as[MAX_N];SegTreeMax<int,MAX_E2> st;/* subroutines *//* main */int main() {int n;scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%d", as + i);int m = n - D + 1;st.init(m);int sum = 0;for (int i = 0; i < D - 1; i++) sum += as[i];for (int i = 0, j = D - 1; j < n; i++, j++) {sum += as[j];st.set(i, sum);sum -= as[i];}st.setall();int qn;scanf("%d", &qn);while (qn--) {int ti, vi;scanf("%d%d", &ti, &vi);ti--;int li = max(ti - D + 1, 0), ri = ti + 1;int d = vi - as[ti];st.add_range(li, ri, d);as[ti] = vi;printf("%d\n", st.nodes[0]);}return 0;}