Codeforces #169 Div2 C "Little Girl and Maximum Sum"
問題
要素数Nの整数の配列がある。
また、配列のインデックスLからRまでの総和を求めよという
クエリがQ個ある。
クエリの結果の合計値が最も大きくなるように
配列を並べ替えた時、その合計値を返せ。
制約
1 <= N,Q <= 2 * 10^5
1 <= 整数配列の値 <= 2 * 10^5
考えた事
クエリ一個一個調べてって、
このインデックスは何回足されるか記憶する。
何回足されるかと与えられた配列を大きい順にソートして、
計算すればいいだけ。楽勝w
ソースかきかき
計算量20万 * 20万 = 400億やん・・・むりやん・・・
タイムアップ
いもす法 使おう
この問題の場合、
Lはそのインデックスから+1になるよ
Rはそのインデックスの次のインデックスから-1になるよ
という感じでメモしてけばよい。
計算量はメモをとるときにO(Q)
各インデックスの回数を調べるのにO(N)
全体としてO(Q+N)?
まあいける
今回は1次元だったけど、
四角形を重ねていって最終的な面積いくつ?
みたいな2次元でもいもす法は使えるらしい。
ソースコード
typedef long long ll; const int MAX_N = 200000; int dansa[MAX_N+2]; int takasa[MAX_N+1]; int main() { //ifstream in( "data.txt" ); istream& in = cin; int N, Q; in >> N >> Q; priority_queue<int> arr; for( int i = 0; i < N; i++ ){ int t; in >> t; arr.push(t); } // 各インデックスの使われる回数増えた減ったをメモ memset( dansa, 0, sizeof(dansa)); for( int i = 0; i < Q; i++ ){ int s, e; in >> s >> e; dansa[s]++; dansa[e+1]--; } // 使われる回数ごとにそれが何個あるか取得 memset( takasa, 0, sizeof(takasa) ); int h = 0; for( int i = 0; i <= N; i++ ){ h += dansa[i]; takasa[h]++; } ll res = 0; for( int h = MAX_N; h >= 1; h-- ){ int num = takasa[h]; ll sum = 0; for( int i = 0; i < num; i++ ){ sum += arr.top(); arr.pop(); } res += sum * h; } cout << res << endl; }