結果

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

ソースコード

diff #
raw source code 

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

const int INF = 1e9 + 5;

struct SegmentTree {
    int N;
    vector<vector<int>> data;

    SegmentTree(const vector<int>& A) {
        N = 1;
        while (N < A.size()) N <<= 1;
        data.resize(2 * N);
        for (int i = 0; i < A.size(); i++) data[i + N].push_back(A[i]);
        for (int i = N - 1; i > 0; i--) {
            data[i].resize(data[2 * i].size() + data[2 * i + 1].size());
            merge(data[2 * i].begin(), data[2 * i].end(),
                  data[2 * i + 1].begin(), data[2 * i + 1].end(),
                  data[i].begin());
        }
    }

    void update(int i, int x) {
        i += N;
        data[i] = { x };
        for (i >>= 1; i > 0; i >>= 1) {
            data[i].clear();
            merge(data[2 * i].begin(), data[2 * i].end(),
                  data[2 * i + 1].begin(), data[2 * i + 1].end(),
                  back_inserter(data[i]));
        }
    }

    int count_ge(int l, int r, int x) {
        l += N;
        r += N + 1;
        int res = 0;
        while (l < r) {
            if (l & 1) {
                res += data[l].end() - lower_bound(data[l].begin(), data[l].end(), x);
                l++;
            }
            if (r & 1) {
                --r;
                res += data[r].end() - lower_bound(data[r].begin(), data[r].end(), x);
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }

    int query_median(int l, int r) {
        int total = r - l + 1;
        int kth = (total + 1) / 2;
        int low = 1, high = 1e9;
        while (low < high) {
            int mid = (low + high + 1) / 2;
            if (count_ge(l, r, mid) >= kth) low = mid;
            else high = mid - 1;
        }
        return low;
    }
};

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

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

    SegmentTree tree(A);

    while (Q--) {
        int type, i, x, l, r;
        cin >> type;
        if (type == 1) {
            cin >> i >> x;
            tree.update(i - 1, x);
        } else {
            cin >> l >> r;
            cout << tree.query_median(l - 1, r - 1) << "\n";
        }
    }
}
0