Codeforces #182, Division 2, B : Eugeny and Play List

問題文

http://codeforces.com/contest/302/problem/B

概要

n 種類の曲からなるプレイリストがある。
各曲の長さは であり、連続して 回聴く。
ある時間 v が m 個与えられるので、それぞれについてその瞬間に再生されている曲の番号を答えよ。
v は昇順に与えられる。

解法

はじめに、各曲について再生が始まる時間と終わる時間を求めておきます。
これは、曲の再生が終わる時間は、前の曲が終わる時間に t * c を足すと求まります。

次に、各 v について再生中の曲を求める方法です。
毎回先頭から調べると になって間に合いませんが、着目するべき曲が前に戻ることはありません。
従って、どこまで調べたかを覚えておいてそこから探索を始めるようにすると、（この着目する曲は後ろにしか動かないので）全体で になります。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define PB( n ) push_back( n )

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

	int n, m;
	cin >> n >> m;

	VI times( 1, 0 );
	REP( i, 0, n )
	{
		int c, t;
		cin >> c >> t;
		times.PB( times.back() + t * c );
	}

	int cur = 0;
	REP( i, 0, m )
	{
		int v;
		cin >> v;

		while ( !( times[ cur ] <= v && v <= times[ cur + 1 ] ) )
		{
			cur++;
		}

		cout << cur + 1 << endl;
	}

	return 0;
}