Codeforces #232, Division 2, A : On Segment's Own Points

問題文

http://codeforces.com/contest/397/problem/A

概要

　数直線上の区間が n 個与えられ、i ( 1-based ) 番の区間は である。1 番の区間に含まれ、他の区間に含まれないような部分の長さを求めよ。

解法

　数えたいのは隣り合う整数点の間に位置する部分ですが、情報は整数点で与えられます。従って、この差をうまいこと吸収する必要があります。
　例えば、この問題の場合与えられる区間を開区間と考えても答えは変わらないので、与えられるのほんの少し左とほんの少し右にずらした部分を別の点として扱うといい感じになります。これは、座標を全て二倍してあげると扱いやすくなります。その状態で 1 番以外の区間に被覆される回数を全て数えた後、1 番の区間に含まれる部分について、全く被覆されていない部分を数え、最後に 1 / 2 をかけたものが答えです。

コード

typedef vector<int> VI;

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

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

	int n;
	cin >> n;

	VI ls( n ), rs( n );
	REP( i, 0, n )
	{
		cin >> ls[i] >> rs[i];
	}

	VI counts( 202 );
	REP( i, 1, n )
	{
		REP( j, ls[i] * 2 + 1, rs[i] * 2 + 1 )
		{
			counts[j]++;
		}
	}
	
	int res = 0;
	REP( i, ls[0] * 2 + 1, rs[0] * 2 + 1 )
	{
		res += !counts[i];
	}

	cout << res / 2 << endl;

	return 0;
}