結果

問題 No.875 Range Mindex Query
ユーザー fura
提出日時 2020-06-01 03:28:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,168 bytes
コンパイル時間 2,768 ms
コンパイル使用メモリ 197,056 KB
最終ジャッジ日時 2025-01-10 20:13:14
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:48:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   48 |         int n; scanf("%d",&n);
      |                ~~~~~^~~~~~~~~
main.cpp:49:23: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   49 |         rep(i,n) scanf("%d",&A[i]);
      |                  ~~~~~^~~~~~~~~~~~
main.cpp:54:21: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   54 |         int q; scanf("%d",&q);
      |                ~~~~~^~~~~~~~~
main.cpp:56:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   56 |                 int type,l,r; scanf("%d%d%d",&type,&l,&r); l--; r--;
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int A[100000];

class segment_tree{
	int n;
	vector<int> dat;
	int query(int l,int r,int a,int b,int u){
		if(l<=a && b<=r) return dat[u];
		int res=-1;
		int c=(a+b)/2;
		if(l<c && a<r){
			int tmp=query(l,r,a,c,2*u+1);
			if(res==-1 || A[res]>A[tmp]) res=tmp;
		}
		if(l<b && c<r){
			int tmp=query(l,r,c,b,2*u+2);
			if(res==-1 || A[res]>A[tmp]) res=tmp;
		}
		return res;
	}
public:
	segment_tree(int N){
		for(n=1;n<N;n*=2);
		dat.assign(2*n-1,0);
	}
	void update(int u,int val){
		u+=n-1;
		dat[u]=val;
		while(u>0){
			u=(u-1)/2;
			if(A[dat[2*u+1]]<=A[dat[2*u+2]]){
				dat[u]=dat[2*u+1];
			}
			else{
				dat[u]=dat[2*u+2];
			}
		}
	}
	int query(int l,int r){ return query(l,r,0,n,0); }
};

int main(){
	int n; scanf("%d",&n);
	rep(i,n) scanf("%d",&A[i]);

	segment_tree ST(n);
	rep(i,n) ST.update(i,i);

	int q; scanf("%d",&q);
	rep(_,q){
		int type,l,r; scanf("%d%d%d",&type,&l,&r); l--; r--;
		if(type==1){
			int i=ST.query(l,l+1);
			int j=ST.query(r,r+1);
			ST.update(l,j);
			ST.update(r,i);
		}
		else{
			printf("%d\n",ST.query(l,r)+1);
		}
	}

	return 0;
}
0