結果
問題 | No.631 Noelちゃんと電車旅行 |
ユーザー | polylogK |
提出日時 | 2018-01-01 14:51:29 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 356 ms / 2,000 ms |
コード長 | 1,897 bytes |
コンパイル時間 | 1,489 ms |
コンパイル使用メモリ | 169,456 KB |
実行使用メモリ | 7,808 KB |
最終ジャッジ日時 | 2024-10-02 09:23:53 |
合計ジャッジ時間 | 8,957 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 271 ms
5,248 KB |
testcase_01 | AC | 356 ms
7,552 KB |
testcase_02 | AC | 352 ms
7,808 KB |
testcase_03 | AC | 355 ms
7,552 KB |
testcase_04 | AC | 353 ms
7,552 KB |
testcase_05 | AC | 352 ms
7,680 KB |
testcase_06 | AC | 141 ms
5,504 KB |
testcase_07 | AC | 77 ms
5,632 KB |
testcase_08 | AC | 266 ms
7,552 KB |
testcase_09 | AC | 312 ms
5,504 KB |
testcase_10 | AC | 214 ms
7,552 KB |
testcase_11 | AC | 192 ms
5,632 KB |
testcase_12 | AC | 238 ms
7,680 KB |
testcase_13 | AC | 231 ms
5,248 KB |
testcase_14 | AC | 111 ms
5,248 KB |
testcase_15 | AC | 196 ms
5,248 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 2 ms
5,248 KB |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | AC | 2 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
ソースコード
#include <bits/stdc++.h> #define REP(i,a,b) for(int i=(a);i<(b);i++) #define RREP(i,a,b) for(int i=(a);i>=(b);i--) #define pq priority_queue #define P pair<int,int> #define P2 pair<int,P> #define P3 pair<int,P2> typedef long long ll; typedef long double ld; using namespace std; const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0}; const ll LINF=1e18; const ld PI=abs(acos(-1)); int n,m,a,b,c,t[100010]; int sz; ll seg[400010]; ll seg_add[400010]; int get_size(int n); ll unit(); ll func(ll a,ll b); int build(int n); int update(int k,int x); //0-indexed int _range_add(int a,int b,int x,int k,int l,int r); int range_add(int a,int b,int x); ll _get(int a,int b,int k,int l,int r); ll get(int a,int b); //[a,b) int main(){ cin >> n; build(n); REP(i,0,n-1) cin >> a,update(i,a+(n-i-1)*3); cin >> m; REP(i,0,m){ cin >> a >> b >> c; range_add(a-1,b,c); cout << get(0,n) << endl; } return 0; } int get_size(int n){ int res=0; while(n) n=n>>1,res++; return (1<<res); } ll unit(){ return -LINF; } ll func(ll a,ll b){ return max(a,b); } int build(int n){ sz=get_size(n); REP(i,0,2*sz) seg[i]=unit(); REP(i,0,2*sz) seg_add[i]=0; return 0; } int update(int k,int x){ k+=sz-1; seg[k]=x; while(k){ k=(k-1)>>1; seg[k]=func(seg[k*2+1],seg[k*2+2]); } return 0; } int _range_add(int a,int b,int x,int k,int l,int r){ if(b<=l||r<=a) return 0; if(a<=l&&r<=b){seg_add[k]+=x; return 0;} _range_add(a,b,x,2*k+1,l,(l+r)>>1); _range_add(a,b,x,2*k+2,(l+r)>>1,r); seg[k]=func(seg[2*k+1]+seg_add[2*k+1], seg[2*k+2]+seg_add[2*k+2]); return 0; } int range_add(int a,int b,int x){ return _range_add(a,b,x,0,0,sz); } ll _get(int a,int b,int k,int l,int r){ if(b<=l||r<=a) return unit(); if(a<=l&&r<=b) return seg[k]+seg_add[k]; return func(_get(a,b,2*k+1,l,(l+r)>>1), _get(a,b,2*k+2,(l+r)>>1,r))+seg_add[k]; } ll get(int a,int b){ return _get(a,b,0,0,sz); }