結果

問題 No.924 紲星
コンテスト
ユーザー arknave
提出日時 2019-11-08 22:48:33
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,821 bytes
コンパイル時間 1,940 ms
コンパイル使用メモリ 175,580 KB
実行使用メモリ 14,592 KB
最終ジャッジ日時 2024-09-15 01:57:35
合計ジャッジ時間 7,971 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

constexpr int MAXN = 2e5 + 5;
int n, q;
int a[MAXN];
int l[MAXN], r[MAXN], order[MAXN];
ll ans[MAXN];

struct TwoSet {
    multiset<int> left, right;
    ll left_sum, right_sum;

    TwoSet(): left_sum(0), right_sum(0) {}

    void balance() {
        while (!right.empty() and !left.empty() and *begin(right) < *prev(end(left))) {
            auto it = begin(right);

            left_sum += *it;
            right_sum -= *it;

            left.insert(*it);
            right.erase(it);
        }

        while (left.size() > right.size()) {
            auto it = prev(end(left));

            right_sum += *it;
            left_sum -= *it;

            right.insert(*it);
            left.erase(it);
        }

        while (!right.empty() and left.size() + 1 < right.size()) {
            auto it = begin(right);

            left_sum += *it;
            right_sum -= *it;

            left.insert(*it);
            right.erase(it);
        }
    }

    void add(int x) {
        if (right.empty() or x > *begin(right)) {
            right_sum += x;
            right.insert(x);
        } else {
            left_sum += x;
            left.insert(x);
        }

        balance();
    }

    void remove(int x) {
        if (!right.empty() and x >= *begin(right)) {
            auto it = right.find(x);
            assert(it != end(right));
            right_sum -= *it;
            right.erase(it);
        } else if (!left.empty()) {
            auto it = left.find(x);
            assert(it != end(left));
            left_sum -= *it;
            left.erase(it);
        } else {
            assert(false);
        }

        balance();
    }

    ll score() const {
        int med = *begin(right);
        return (1LL * left.size() * med - left_sum)
            + (right_sum - 1LL * right.size() * med);
    }
};

void move_left(TwoSet& ts, int& left_ptr, int query) {
    while (left_ptr < l[query]) {
        ts.remove(a[left_ptr++]);
    }
    while (left_ptr > l[query]) {
        ts.add(a[--left_ptr]);
    }
}

void move_right(TwoSet& ts, int& right_ptr, int query) {
    while (right_ptr < r[query]) {
        ts.add(a[++right_ptr]);
    }

    while (right_ptr > r[query]) {
        ts.remove(a[right_ptr--]);
    }
}

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

    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    for (int i = 0; i < q; ++i) {
        cin >> l[i] >> r[i];
        --l[i]; --r[i];
    }

    const int SQRTN = sqrt(n);
    iota(order, order + q, 0);
    sort(order, order + q, [&](int x, int y) {
        int b1 = l[x] / SQRTN;
        int b2 = l[y] / SQRTN;
        if (b1 != b2) {
            return b1 < b2;
        }
        return b1 % 2 ? r[x] > r[y] : r[x] < r[y];
    });

    TwoSet ts;
    int left_ptr = 0;
    int right_ptr = -1;
    for (int i = 0; i < q; ++i) {
        int query = order[i];
        // cout << "query " << l[query] << " " << r[query] << '\n';
        if (l[query] < left_ptr and r[query] < right_ptr) {
            move_left(ts, left_ptr, query);
            move_right(ts, right_ptr, query);
        } else {
            move_right(ts, right_ptr, query);
            move_left(ts, left_ptr, query);
        }
        assert(left_ptr == l[query]);
        assert(right_ptr == r[query]);
        /*
        for (int x : ts.left) {
            cout << x << ' ';
        }
        for (int x : ts.right) {
            cout << x << ' ';
        }
        cout << '\n';
        */
        ans[query] = ts.score();
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }

    return 0;
}
0