TopCoder SRM 586, Division 2, Level 2 : PiecewiseLinearFunctionDiv2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12698&rd=15698

概要

Division 1, Level 1 と同様の関数 f がある。
query に含まれる数について、query[i] = f(x) を満たす x の個数を求めよ。
無限に存在する場合は -1 で示せ。

解法

query[i] の値を q とします。
Y[i] == q かつ Y[ i + 1 ] == q を満たす i が存在するとき、q に対する答えは -1 になります。
それ以外の時は高々有限個の解しか持たないので、Y を走査しつつ解の個数を数えればよいです。

コード

typedef vector<int> VI;

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

class PiecewiseLinearFunctionDiv2
{
public:
	vector <int> countSolutions( vector <int> Y, vector <int> query )
	{
		VI res;
		REP( i, 0, query.size() )
		{
			res.PB( solve( Y, query[i] ) );
		}
		return res;
	}

	int solve( const VI &Y, const int target )
	{
		int res = 0;
		REP( i, 0, Y.size() - 1 )
		{
			if ( Y[i] == target && Y[ i + 1 ] == target )
			{
				return -1;
			}

			res += min( Y[i], Y[ i + 1 ] ) <= target && target <= max( Y[i], Y[ i + 1 ] );
		}
		REP( i, 1, Y.size() - 1 )
		{
			res -= Y[i] == target;
		}
		return res;
	}
};