Codeforces 167, Divison 2, C : Dima and Staircase

問題文

http://codeforces.com/contest/272/problem/C

概要

ブロックが階段状に積まれている。
ここに、m 個のブロックが落ちてくる。
落ちてきたブロックは、底面が階段または先行して落ちてきたブロックに当たったところで止まる。
階段の状態と、落ちてくるブロックの情報が与えられるので、各ブロックが停止する高さを全て出力せよ。

解法

問題設定より、落ちてくるブロックが停止するのは、左端か右端が何かに当たる場合です。
従って、左端の高さと、変化した階段の高さだけを記憶しておけばクエリに答えることができます。

コード

typedef long long LL;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define EACH( v, c ) for ( auto &v : c )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	vector<LL> as( n );
	EACH( a, as )
	{
		cin >> a;
	}

	LL m, left = as[0];
	cin >> m;

	REP( i, 0, m )
	{
		int w, h;
		cin >> w >> h;

		cout << max( left, as[ w - 1 ] ) << endl;;
		as[ w - 1 ] += h;
		left = max( left + h, as[ w - 1 ] );
	}

	return 0;
}