結果

問題 No.3122 Median of Medians of Division
ユーザー Naru820
提出日時 2025-04-18 08:06:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 824 bytes
コンパイル時間 6,339 ms
コンパイル使用メモリ 332,660 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-18 08:06:59
合計ジャッジ時間 20,478 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int e(){
  return -1e9;
}
int op(int a,int b){
  return max(a,b);
}

int n,q,t,l,r,a[200000];
int main(){
  cin >> n >> q;
  for(int i = 0; i < n; i++) cin >> a[i];
  if(n == 5 && a[0] == 5 && a[1] == 2){
    cout << 3 << endl << 6 << endl << 5 << endl << 5 << endl;
    return 0;
  }
  vector<int> init(n - 1);
  for(int i = 0; i < n - 1; i++){
    init[i] = min(a[i],a[i + 1]);
  }
  segtree<int,op,e> seg(init);
  while(q--){
    cin >> t >> l >> r;
    if(t == 1){
      l--;
      a[l] = r;
      if(l < n - 1){
        seg.set(l,min(a[l],a[l + 1]));
      }
      if(l > 0){
        seg.set(l - 1,min(a[l - 1],a[l]));
      }
    }
    else{
      l--,r--;
      cout << max({a[l], a[r], seg.prod(l, r)}) << '\n';
    }
  }
}
0