結果

問題 No.3122 Median of Medians of Division
コンテスト
ユーザー Yu_212
提出日時 2025-04-20 02:30:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 4,279 bytes
コンパイル時間 3,809 ms
コンパイル使用メモリ 296,908 KB
実行使用メモリ 654,964 KB
最終ジャッジ日時 2025-04-20 02:30:17
合計ジャッジ時間 12,568 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other MLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template<typename T>
ostream& operator<<(ostream &o, vector<T> v) {
    for (int i = 0; i < v.size(); i++)
        o << v[i] << (i+1<v.size()?" ":"");
    return o;
}

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

// Segment tree of multisets to count >= x in range
struct SegTree {
    int n;
    vector<multiset<int>> st;
    SegTree(int _n): n(_n) {
        st.resize(4*n+4);
    }
    // insert initial value at pos
    void insert_val(int node, int l, int r, int pos, int val) {
        st[node].insert(val);
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (pos <= mid) insert_val(node<<1, l, mid, pos, val);
        else insert_val(node<<1|1, mid+1, r, pos, val);
    }
    // update oldv -> newv at pos
    void update_val(int node, int l, int r, int pos, int oldv, int newv) {
        auto it = st[node].find(oldv);
        if (it != st[node].end()) st[node].erase(it);
        st[node].insert(newv);
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (pos <= mid) update_val(node<<1, l, mid, pos, oldv, newv);
        else update_val(node<<1|1, mid+1, r, pos, oldv, newv);
    }
    // count elements >= x in [ql, qr]
    int count_ge(int node, int l, int r, int ql, int qr, int x) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) {
            auto it = st[node].lower_bound(x);
            return distance(it, st[node].end());
        }
        int mid = (l + r) >> 1;
        return count_ge(node<<1, l, mid, ql, qr, x)
             + count_ge(node<<1|1, mid+1, r, ql, qr, x);
    }
};

struct Query { int type, a, b; };

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

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

    vector<Query> queries(Q);
    for (int i = 0; i < Q; i++){
        cin >> queries[i].type >> queries[i].a >> queries[i].b;
    }

    // build adjacent arrays: D1 for min (for adjacent >=m pairs), E for max (for adjacent <m pairs)
    vector<int> D1(max(N,1)), E(max(N,1));
    for (int i = 1; i < N; i++){
        D1[i] = min(A[i], A[i+1]);
        E[i]  = max(A[i], A[i+1]);
    }

    // build segment trees
    SegTree stA(N), stD1(max(N-1,1)), stE(max(N-1,1));
    for (int i = 1; i <= N; i++) stA.insert_val(1, 1, N, i, A[i]);
    for (int i = 1; i < N; i++){
        stD1.insert_val(1, 1, N-1, i, D1[i]);
        stE.insert_val(1, 1, N-1, i, E[i]);
    }

    // update function for neighbors
    auto updAdj = [&](int pos){
        if (pos < 1 || pos >= N) return;
        int old_d1 = D1[pos], old_e = E[pos];
        int new_d1 = min(A[pos], A[pos+1]);
        int new_e  = max(A[pos], A[pos+1]);
        if (old_d1 != new_d1)
            stD1.update_val(1, 1, N-1, pos, old_d1, new_d1);
        if (old_e != new_e)
            stE.update_val(1, 1, N-1, pos, old_e, new_e);
        D1[pos] = new_d1;
        E[pos]  = new_e;
    };

    // check if median-of-medians >= m
    auto check = [&](int m, int l, int r){
        int len = r - l + 1;
        int ones = stA.count_ge(1, 1, N, l, r, m);
        int a = (l < r ? stD1.count_ge(1, 1, N-1, l, r-1, m) : 0);
        int total_pairs = r - l;
        int z = total_pairs - (l < r ? stE.count_ge(1, 1, N-1, l, r-1, m) : 0);
        int left_zero = (A[l] < m ? 1 : 0);
        int seg0 = ((len) - a - z + left_zero) / 2;
        // cout << l << " " << r <<" " << m<< " " << ones << ' ' << seg0 << " " << a << " " << z << '\n';

        return ones > seg0;
    };

    // process queries
    for (auto &q : queries){
        if (q.type == 1){
            int i = q.a;
            int newv = q.b;
            stA.update_val(1, 1, N, i, A[i], newv);
            A[i] = newv;
            updAdj(i-1);
            updAdj(i);
        } else {
            // cout << A << endl;
            int l = q.a, r = q.b;
            int lo = 1, hi = 1000000001, ans = 1;
            while (lo <= hi){
                int mid = lo + (hi - lo) / 2;
                if (check(mid, l, r)){
                    ans = mid;
                    lo = mid + 1;
                } else hi = mid - 1;
            }
            cout << ans << '\n';
        }
    }

    return 0;
}
0