結果

問題 No.631 Noelちゃんと電車旅行
ユーザー Kutimoti_TKutimoti_T
提出日時 2018-01-06 20:53:46
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 346 ms / 2,000 ms
コード長 1,846 bytes
コンパイル時間 856 ms
コンパイル使用メモリ 66,560 KB
実行使用メモリ 9,600 KB
最終ジャッジ日時 2024-04-10 07:48:42
合計ジャッジ時間 6,870 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 254 ms
5,248 KB
testcase_01 AC 331 ms
9,472 KB
testcase_02 AC 333 ms
9,600 KB
testcase_03 AC 342 ms
9,600 KB
testcase_04 AC 331 ms
9,600 KB
testcase_05 AC 346 ms
9,472 KB
testcase_06 AC 150 ms
6,400 KB
testcase_07 AC 75 ms
6,016 KB
testcase_08 AC 254 ms
8,960 KB
testcase_09 AC 302 ms
7,168 KB
testcase_10 AC 220 ms
8,832 KB
testcase_11 AC 192 ms
6,528 KB
testcase_12 AC 232 ms
8,960 KB
testcase_13 AC 223 ms
5,504 KB
testcase_14 AC 101 ms
5,376 KB
testcase_15 AC 196 ms
5,632 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

struct LazySegment{
	
	int n;
	vector<ll> node,lazy;

	LazySegment(vector<ll>& v)
	{
		int sz = (int)v.size();
		n = 1;
		while(n < sz) n*= 2;
		node.resize(2 * n - 1);
		lazy.resize(2 * n - 1,0);

		for(int i = 0;i < sz;i++) node[i + n - 1] = v[i] + (sz - i) * 3;
		for(int i = n - 2;i >=0;i--) node[i] = max(node[i * 2 + 1],node[i * 2 + 2]);

	}	

	void eval(int k,int l,int r)
	{
		if(lazy[k] != 0)
		{
			node[k] += lazy[k];


			if(r - l > 1)
			{
				lazy[2 * k + 1] += lazy[k];
				lazy[2 * k + 2] += lazy[k];
			}
			lazy[k] = 0;
		}
	}

	void add(int a,int b,ll x,int k = 0,int l = 0,int r = -1)
	{
		if(r < 0) r = n;

		eval(k,l,r);

		if(r <= a || b <= l) return;

		if(a <= l && r <= b)
		{
			lazy[k] += x;
			eval(k,l,r);
		}
		else
		{
			add(a,b,x,2 * k + 1,l,(l + r) / 2);
			add(a,b,x,2 * k + 2,(l + r) / 2,r);
			node[k] = max(node[2 * k + 1] , node[2 * k + 2]);
		}
	}
	
	ll getMax(int a,int b,int k = 0,int l = 0,int r = -1)
	{
		if(r < 0) r = n;

		eval(k,l,r);

		if(r <= a || b <= l) return -100000000;
		if(a <= l && r <= b) return node[k];

		ll vl = getMax(a,b,2*k+1,l,(l + r)/2);
		ll vr = getMax(a,b,2*k+2,(l + r)/2,r);

		return max(vl,vr);
	}

	void Print()
	{
		cout << endl;
		ll cou = 1;
		for(int i = 0;i < node.size();i++)
		{
			if(i == cou)
			{
				cout << endl;
				cou = 2 * cou + 1;
			}
			cout << node[i] << "+" << lazy[i] << " ";
		}
	}
};


int N;
vector<ll> T;
int M;
int L[100001];
int R[100001];
ll D[100001];

int main()
{
	cin >> N;
	T.resize(N - 1);
	for(int i = 0;i < N - 1;i++)
	{
		cin >> T[i];
	}

	cin >> M;

	for(int i = 0;i < M;i++)
	{
		cin >> L[i] >> R[i] >> D[i];
	}

	LazySegment seg(T);

	for(int i = 0;i < M;i++)
	{
		seg.add(L[i] - 1,R[i],D[i]);
		cout << seg.getMax(0,N) << endl;
	}
	return 0;
}
0