結果

問題 No.3198 Monotonic Query
コンテスト
ユーザー daiota
提出日時 2025-07-12 00:05:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 187 ms / 3,000 ms
コード長 924 bytes
コンパイル時間 1,700 ms
コンパイル使用メモリ 160,516 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-07-12 10:56:26
合計ジャッジ時間 6,813 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(int i=0;i<int(n);i++)



#define T 200010
#define INF (1<<31)-1
int n,tree[4*T];

void init(int N){
  n=1;
  while(n<N) n*=2;
  REP(i,2*n-1) tree[i]=0;
}

void update(int k, int a){
  k+=n-1;
  tree[k]=a;
  while(k>0){
    k=(k-1)/2;
    tree[k]=max(tree[2*k+1], tree[2*k+2]);
  }
}

int query(int a, int b, int k, int l, int r){
  if(r<=a || b<=l) return 0;
  if(a<=l && r<=b) return tree[k];
  else return max(query(a,b,2*k+1,l,(l+r)/2),query(a,b,2*k+2,(l+r)/2,r));
}






int main(void){
	cin.tie(nullptr);  ios_base::sync_with_stdio(false);
	int i,j;





	int Q;
	cin >> Q;


	init(Q);

	int s=0;
	while(Q--){

		int t;
		cin >> t;


		if(t==1){
			int x;
			cin >> x;
			update(s,x);
			s++;

		}else{
			int k;
			cin >> k;
			cout << query(s-k,s,0,0,n) << endl;

		}

	}











	return 0;

}
0