結果

問題 No.3122 Median of Medians of Division
ユーザー Naru820
提出日時 2025-04-16 17:56:10
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,102 bytes
コンパイル時間 3,432 ms
コンパイル使用メモリ 272,432 KB
実行使用メモリ 20,040 KB
最終ジャッジ日時 2025-04-17 09:11:57
合計ジャッジ時間 17,731 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

//O(QNlogN)
#include <bits/stdc++.h>
using namespace std;

int n,q,a[200000],t,l,r;
int main() {
    cin >> n >> q;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < q; i++){
        cin >> t >> l >> r;
        if(t == 1){
            l--;
            a[l] = r;
        }
        else{
            l--,r--;
            int isok = 1,isng = 1e9 + 1;
            while(isng - isok > 1){
                int mid =(isok + isng) / 2;
                int sum = 0,now = 0;
                for(int i = l; i <= r; i++){
                    if(a[i] >= mid){
                        sum++;
                        if(now){
                            sum--;
                            now = 0;
                        }
                    }
                    else{
                    now = 1;
                    }
                }
                if(now) sum--;
                if(sum > 0){
                    isok = mid;
                }
                else{
                    isng = mid;
                }
            }
        cout << isok << endl;
        }
    }
}
0