Codeforces #169, C : Little Girl and Maximum Sum

問題文

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

概要

配列 a に対する次のようなクエリがある。

• 区間 [ l, r ) の総和を計算する

ここで q 個のクエリがくるので、クエリを受け付ける前に配列を並び替えてクエリの結果の総和を最大化したい。
そうした場合のクエリの結果の総和の最大値を求めよ。

解法

まず、各インデックスについて、クエリの対象に含まれる回数を求めます。
愚直に実装すると TLE してしまうので、この部分はいもす法を用います。
その後、回数の多い順に a から Greedy に割り当てます。

コード

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()

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

	int n, q;
	cin >> n >> q;

	VI as( n );
	FOR( a, as )
	{
		cin >> a;
	}

	VI qs( 200001 );
	REP( i, 0, q )
	{
		int l, r;
		cin >> l >> r;
		l--;

		qs[l]++;
		qs[r]--;
	}

	vector<LL> counts( 1, 0 );
	partial_sum( ALL( qs ), back_inserter( counts ) );

	sort( ALL( counts ), greater<int>() );
	sort( ALL( as ), greater<int>() );

	ULL res = 0;
	REP( i, 0, n )
	{
		res += as[i] * counts[i];
	}

	cout << res << endl;

	return 0;
}