結果

問題 No.3122 Median of Medians of Division
コンテスト
ユーザー karashi-0086A2
提出日時 2025-04-20 19:46:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,632 bytes
コンパイル時間 2,782 ms
コンパイル使用メモリ 211,500 KB
実行使用メモリ 24,160 KB
最終ジャッジ日時 2025-04-20 19:47:04
合計ジャッジ時間 11,206 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

const int BLOCK = 450;  // √N程度

struct Query {
    int l, r, time, id;
    bool operator<(const Query& other) const {
        if (l / BLOCK != other.l / BLOCK) return l < other.l;
        if (r / BLOCK != other.r / BLOCK) return r < other.r;
        return time < other.time;
    }
};

vector<int> A, original;
vector<pair<int, int>> updates;
multiset<int> leftSet, rightSet;

void balance() {
    while (leftSet.size() > rightSet.size()) {
        auto it = prev(leftSet.end());
        rightSet.insert(*it);
        leftSet.erase(it);
    }
    while (rightSet.size() > leftSet.size() + 1) {
        auto it = rightSet.begin();
        leftSet.insert(*it);
        rightSet.erase(it);
    }
}

void add(int x) {
    if (rightSet.empty() || x >= *rightSet.begin()) rightSet.insert(x);
    else leftSet.insert(x);
    balance();
}

void remove(int x) {
    if (rightSet.find(x) != rightSet.end()) rightSet.erase(rightSet.find(x));
    else leftSet.erase(leftSet.find(x));
    balance();
}

void applyUpdate(int idx, int newValue, int& oldValue) {
    oldValue = A[idx];
    remove(oldValue);
    A[idx] = newValue;
    add(newValue);
}

void revertUpdate(int idx, int oldValue) {
    remove(A[idx]);
    A[idx] = oldValue;
    add(oldValue);
}

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

    int N, Q;
    cin >> N >> Q;
    A.resize(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    vector<Query> queries;
    vector<int> answers(Q);
    int nowTime = 0;

    for (int i = 0; i < Q; i++) {
        int type, a, b;
        cin >> type >> a >> b;
        if (type == 1) {
            updates.emplace_back(a - 1, b);
        } else {
            queries.push_back({a - 1, b - 1, (int)updates.size(), i});
        }
    }

    sort(queries.begin(), queries.end());

    int l = 0, r = -1, t = 0;
    original = A;
    for (auto& q : queries) {
        while (t < q.time) {
            int idx = updates[t].first, val = updates[t].second, old;
            applyUpdate(idx, val, old);
            updates[t].second = old; // old値を保存
            t++;
        }
        while (t > q.time) {
            t--;
            int idx = updates[t].first, old = updates[t].second;
            revertUpdate(idx, old);
        }
        while (r < q.r) add(A[++r]);
        while (l > q.l) add(A[--l]);
        while (r > q.r) remove(A[r--]);
        while (l < q.l) remove(A[l++]);

        answers[q.id] = *rightSet.begin();  // 中央値は右側先頭
    }

    for (int i = 0; i < Q; i++) {
        if (answers[i]) cout << answers[i] << '\n';
    }
}
0