結果

問題 No.3122 Median of Medians of Division
ユーザー GOTKAKO
提出日時 2025-04-19 12:20:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,807 bytes
コンパイル時間 2,080 ms
コンパイル使用メモリ 203,396 KB
実行使用メモリ 12,568 KB
最終ジャッジ日時 2025-04-19 12:20:45
合計ジャッジ時間 8,186 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other WA * 20 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template<typename T>
vector<pair<T,long long>> RLE(vector<T> &A){
    if(A.size() == 0) return {};
    vector<pair<T,long long>> ret;
    T back = A.at(0);
    long long streak = 1;
    for(int i=1; i<A.size(); i++){
        if(back == A.at(i)) streak++;
        else{
            ret.push_back({back,streak});
            back = A.at(i); streak = 1;
        }
    }
    ret.push_back({back,streak});
    return ret;
}
vector<pair<char,long long>> RLE(string &s){
    if(s.size() == 0) return {};
    vector<pair<char,long long>> ret;
    char back = s.at(0);
    long long streak = 1;
    for(int i=1; i<s.size(); i++){
        if(back == s.at(i)) streak++;
        else{
            ret.push_back({back,streak});
            back = s.at(i); streak = 1;
        }
    }
    ret.push_back({back,streak});
    return ret;
}

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

    int N,Q; cin >> N >> Q;
    vector<int> A(N);
    for(auto &a : A) cin >> a;

    if(N*Q >= 1001001) return 0;
    while(Q--){
        int t; cin >> t;
        if(t == 1){
            int p,x; cin >> p >> x; p--;
            A.at(p) = x;
        }
        if(t == 2){
            int l,r; cin >> l >> r; l--;
            int low = 0,high = 1001001001;
            while(high-low > 1){
                int mid = (high+low)/2;
                vector<int> B;
                for(int i=l; i<r; i++) B.push_back(A.at(i)>=mid);
                auto C = RLE(B);
                int ok = 0,ng = 0;
                for(auto [a,len] : C){
                    if(a == 1) ok += len;
                    else ng += 1;
                }
                if(ok > ng) low = mid;
                else high = mid;
            }
            cout << low << "\n";
        }
    }
}
0