結果
問題 | No.631 Noelちゃんと電車旅行 |
ユーザー | ikd |
提出日時 | 2018-01-08 15:24:37 |
言語 | D (dmd 2.106.1) |
結果 |
AC
|
実行時間 | 636 ms / 2,000 ms |
コード長 | 1,660 bytes |
コンパイル時間 | 1,877 ms |
コンパイル使用メモリ | 89,380 KB |
実行使用メモリ | 9,764 KB |
最終ジャッジ日時 | 2023-09-03 17:55:35 |
合計ジャッジ時間 | 9,315 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 210 ms
4,376 KB |
testcase_01 | AC | 636 ms
7,960 KB |
testcase_02 | AC | 634 ms
7,736 KB |
testcase_03 | AC | 636 ms
7,824 KB |
testcase_04 | AC | 636 ms
9,736 KB |
testcase_05 | AC | 634 ms
8,496 KB |
testcase_06 | AC | 185 ms
5,288 KB |
testcase_07 | AC | 88 ms
6,200 KB |
testcase_08 | AC | 436 ms
7,468 KB |
testcase_09 | AC | 471 ms
9,764 KB |
testcase_10 | AC | 326 ms
7,136 KB |
testcase_11 | AC | 300 ms
6,480 KB |
testcase_12 | AC | 378 ms
7,524 KB |
testcase_13 | AC | 275 ms
6,060 KB |
testcase_14 | AC | 73 ms
4,380 KB |
testcase_15 | AC | 264 ms
4,992 KB |
testcase_16 | AC | 1 ms
4,376 KB |
testcase_17 | AC | 2 ms
4,376 KB |
testcase_18 | AC | 2 ms
4,376 KB |
testcase_19 | AC | 2 ms
4,376 KB |
testcase_20 | AC | 1 ms
4,380 KB |
ソースコード
void main(){ import std.stdio, std.string, std.conv, std.algorithm; int n; rd(n); auto t=readln.split.to!(long[]); assert(t.length==(n-1)); auto sqd=new SqD(t); int q; rd(q); while(q--){ int l, r; long d; rd(l, r, d); sqd.radd(l-1, r, d); writeln(sqd.rmax(0, n-1)); } } class SqD{ int sz=1, k=1; long[] buc, bucmax, laz; import std.algorithm; this(long[] a){ auto n=a.length; while(sz*sz<n) sz++; bucmax.length=laz.length=sz; buc.length=(sz*sz); foreach(i; 0..n) buc[i]=a[i]+(n-i)*3; foreach(i; 0..sz) bucmax[i]=reduce!(max)(buc[(i*sz)..((i+1)*sz)]); } void push(int i){ if(laz[i]>0){ buc[(i*sz)..((i+1)*sz)]+=laz[i]; laz[i]=0; } } void radd(int l, int r, long x){ for(auto i=l/sz; i<=r/sz && i*sz<sz*sz; i++){ if(l<=i*sz && (i+1)*sz<=r){ bucmax[i]+=x; laz[i]+=x; }else{ push(i); auto s=max(l, i*sz), t=min(r, (i+1)*sz); buc[s..t]+=x; if(s<t) bucmax[i]=reduce!(max)(buc[(i*sz)..((i+1)*sz)]); } } } long rmax(int l, int r){ long ret=0; for(auto i=l/sz; i<=r/sz && i*sz<sz*sz; i++){ if(l<=i*sz && (i+1)*sz<=r){ ret=max(ret, bucmax[i]); }else{ push(i); auto s=max(l, i*sz), t=min(r, (i+1)*sz); if(s<t) ret=max(ret, reduce!(max)(buc[s..t])); } } return ret; } } void rd(T...)(ref T x){ import std.stdio, std.string, std.conv; auto l=readln.split; assert(l.length==x.length); foreach(i, ref e; x){ e=l[i].to!(typeof(e)); } } void wr(T...)(T x){ import std.stdio; foreach(e; x) write(e, " "); writeln(); }