結果

問題 No.631 Noelちゃんと電車旅行
コンテスト
ユーザー autumn-eel
提出日時 2018-01-05 23:28:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 329 ms / 2,000 ms
コード長 2,124 bytes
コンパイル時間 1,704 ms
コンパイル使用メモリ 169,092 KB
実行使用メモリ 8,944 KB
最終ジャッジ日時 2024-10-02 09:30:49
合計ジャッジ時間 7,290 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

#ifndef MAX
#define MAX 400000
#endif

//Range Add Query+Range Minimum Query
template<class T>
class RAQ_RMQ {
public:
	int n;
	T dat[MAX], lazy[MAX], ZERO, DEFAULT;
	bool(*cmp)(T, T);
	void init(int n_,
		bool(*c)(T, T) = [](int a, int b) {return a < b; }, T d = INT_MAX) {
		cmp = c;
		DEFAULT = d;
		ZERO = T();
		n = 1; while (n < n_)n <<= 1;
		for (int i = 0; i < 2 * n - 1; i++) {
			dat[i] = lazy[i] = ZERO;
		}
	}
	inline void push(int k) {
		dat[k] = dat[k] + lazy[k];
		if (k < n - 1) {
			lazy[k * 2 + 1] = lazy[k * 2 + 1] + lazy[k];
			lazy[k * 2 + 2] = lazy[k * 2 + 2] + lazy[k];
		}
		lazy[k] = ZERO;
	}
	inline void update_node(int k) {
		if (cmp(dat[k * 2 + 1], dat[k * 2 + 2]))dat[k] = dat[k * 2 + 1];
		else dat[k] = dat[k * 2 + 2];
	}
	inline void update(int a, int b, T x, int k, int l, int r) {
		push(k);
		if (r <= a || b <= l)return;
		if (a <= l&&r <= b) {
			lazy[k] = lazy[k] + x; push(k); return;
		}
		update(a, b, x, k * 2 + 1, l, (l + r) / 2);
		update(a, b, x, k * 2 + 2, (l + r) / 2, r);
		update_node(k);
	}
	inline T query(int a, int b, int k, int l, int r) {
		push(k);
		if (r <= a || b <= l)return DEFAULT;
		if (a <= l&&r <= b)return dat[k];
		T lb = query(a, b, k * 2 + 1, l, (l + r) / 2);
		T rb = query(a, b, k * 2 + 2, (l + r) / 2, r);
		update_node(k);
		if (cmp(lb, rb))return lb;
		return rb;
	}
	inline void update(int a, int b, T x) {
		update(a, b, x, 0, 0, n);
	}
	inline void update(int a, T x) {
		update(a, a + 1, x);
	}
	inline T query(int a, int b) {
		return query(a, b, 0, 0, n);
	}
	inline T query(int a) {
		return query(a, a + 1);
	}
};
RAQ_RMQ<ll>seg;
signed main(){
	int n;scanf("%d",&n);
	seg.init(n,[](ll a,ll b){return a>b;},0);
	rep(i,n-1){
		int t;scanf("%d",&t);
		seg.update(i,t+(n-i-1)*3);
	}
	int m;scanf("%d",&m);
	rep(i,m){
		int l,r,d;scanf("%d%d%d",&l,&r,&d);l--;
		seg.update(l,r,d);
		cout<<seg.query(0,n)<<endl;
	}
}
0