Submission #64906

ソースコード

#include<bits/stdc++.h>
using namespace std;
 
#define inf INT_MAX
 
struct segment{
     
    int N;//葉の数
    vector<int> nood;
 
    segment(int n){
        N=2;
        while(N<n){
            N*=2;
        }
        nood.resize(N*2);
        for(int i=0;i<N*2;i++){
            nood[i]=inf;
        }
    }
 
    void update(int a,int b){
        a+=N-1;
        nood[a]=b;
 
        while(a>0){
            a=(a-1)/2;
            nood[a]=min(nood[a*2+1],nood[a*2+2]);
        }
    }
 
    int find(int a,int b){
        return(GetMin(a,b+1,0,0,N));
    }
 
    int GetMin(int a,int b,int i,int l,int r){
        if(a<=l && r<=b){
            return(nood[i]);
        }
        if(b<=l || r<=a){
            return(inf);
        }
        int c1 = GetMin(a,b,i*2+1,l,(l+r)/2);
        int c2 = GetMin(a,b,i*2+2,(l+r)/2,r);
 
        return(min(c1,c2));
    }
};
 
int main(){
    int n;
    cin>>n;
    segment st(n);
 
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        st.update(i,a);
    }
 
    string com;
    cin>>com;
     
    while(com!="exit"){
        int a,b;
        cin>>a>>b;
 
        if(com=="update"){
            st.update(a,b);
        }else{
            cout<<st.find(a,b)<<"\n";
        }
        cin>>com;
    }
    return(0);
}

ステータス

項目	データ
問題	0459 - セグメントツリー練習
ユーザー名	ei2007
投稿日時	2020-12-07 16:30:11
言語	C++17
状態	Accepted
得点	10
ソースコード長	1337 Byte
最大実行時間	57 ms
最大メモリ使用量	1540 KB

セット

	セット	得点	Cases
1	ALL	10 / 10	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
Input01	AC	30 ms	476 KB	1
Input02	AC	25 ms	580 KB	1
Input03	AC	30 ms	548 KB	1
Input04	AC	23 ms	516 KB	1
Input05	AC	20 ms	492 KB	1
Input06	AC	25 ms	592 KB	1
Input07	AC	21 ms	560 KB	1
Input08	AC	23 ms	524 KB	1
Input09	AC	35 ms	608 KB	1
Input10	AC	57 ms	1540 KB	1