結果

問題 No.3122 Median of Medians of Division
コンテスト
ユーザー Naru820
提出日時 2025-06-02 09:59:30
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,473 bytes
コンパイル時間 1,587 ms
コンパイル使用メモリ 134,956 KB
実行使用メモリ 28,276 KB
最終ジャッジ日時 2025-06-02 09:59:45
合計ジャッジ時間 14,600 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <map>

// long long 型のエイリアス
using ll = long long;

// グローバル変数として配列 A を定義
std::vector<ll> A;
int N;

// 判定関数: 中央値の中央値を X 以上にできるかチェックする
// この関数は O((r-l)^2) であり、制約上は低速ですが、アルゴリズムの核となります。
// 実際の提出コードでは、この部分をセグメントツリーで O(log N) に高速化する必要があります。
bool check(ll X, int l, int r) {
    std::vector<int> C;
    for (int i = l - 1; i < r; ++i) {
        C.push_back((A[i] >= X) ? 1 : -1);
    }

    int len = C.size();
    if (len == 0) return false;

    std::vector<int> dp(len + 1, -1e9);
    std::vector<int> prefix_sum(len + 1, 0);
    for (int i = 0; i < len; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + C[i];
    }

    dp[0] = 0;

    for (int i = 1; i <= len; ++i) {
        for (int j = 1; j <= i; ++j) {
            // C の部分列 [j-1, i-1] の和を計算
            int current_sum = prefix_sum[i] - prefix_sum[j - 1];
            int score = (current_sum > 0) ? 1 : -1;
            
            // dp[i] を更新
            if (dp[j - 1] > -1e9) {
                dp[i] = std::max(dp[i], dp[j - 1] + score);
            }
        }
    }

    // k_p - k_n > 0 かどうか
    return dp[len] > 0;
}


int main() {
    // 高速な入出力
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int Q;
    std::cin >> N >> Q;

    A.resize(N);
    // 二分探索の候補となる値を集める
    std::vector<ll> candidates;
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i];
        candidates.push_back(A[i]);
    }
    
    // クエリを先に読み込む
    std::vector<std::tuple<int, int, int>> queries(Q);
    for (int i = 0; i < Q; ++i) {
        int type, p1, p2;
        std::cin >> type >> p1 >> p2;
        queries[i] = {type, p1, p2};
        if (type == 1) {
            candidates.push_back(p2);
        }
    }

    // 候補となる値をソートしてユニークにする
    std::sort(candidates.begin(), candidates.end());
    candidates.erase(std::unique(candidates.begin(), candidates.end()), candidates.end());

    // 各クエリを処理
    for (const auto& q : queries) {
        int type, p1, p2;
        std::tie(type, p1, p2) = q;

        if (type == 1) {
            // クエリタイプ 1: 更新
            A[p1 - 1] = p2;
        } else {
            // クエリタイプ 2: 質問
            int l = p1;
            int r = p2;

            // 答えの候補 `candidates` 上で二分探索
            int low = 0, high = candidates.size() - 1;
            int ans_idx = -1;

            while (low <= high) {
                int mid_idx = low + (high - low) / 2;
                ll X = candidates[mid_idx];
                
                if (check(X, l, r)) {
                    // X 以上を達成可能なら、答えは X かもしれないし、もっと大きいかもしれない
                    ans_idx = mid_idx;
                    low = mid_idx + 1;
                } else {
                    // X 以上を達成不可能なら、答えは X より小さい
                    high = mid_idx - 1;
                }
            }
            std::cout << candidates[ans_idx] << "\n";
        }
    }

    return 0;
}
0