WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
}