oj.uz

답안 #918850

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
918850 2024-01-30T14:37:19 Z vjudge1 Deda (COCI17_deda) C++17
140 / 140
 102 ms 8016 KB 
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=2e5+100;
#else
    const int lim=3e3+100;
#endif
    
#include "bits/stdc++.h"
using namespace std;
    
//#define int int64_t
#define pb push_back
    
const int mod=1e9+7;
using pii=pair<int,int>;
    
struct segtree{
    int tree[4*lim];
    int n;
    segtree(int n):n(n){
        for(int i=0;i<=4*n;i++){
            tree[i]=INT_MAX;
        }
    }
    int P,VAL;
    void update(int l,int r,int node){
        if(l==r){
            tree[node]=VAL;
            return;
        }
        int mid=(l+r)>>1,child=node<<1;
        if(P<=mid)update(l,mid,child);
        else update(mid+1,r,child|1);
        tree[node]=min(tree[child],tree[child|1]);
    }
    void update(int p,int val){
        P=p,VAL=val;
        update(1,n,1);
    }
    int query2(int l,int r,int node){
        if(l==r){
            return l;
        }
        int mid=(l+r)>>1,child=node<<1;
        if(tree[child]<=VAL) return query2(l,mid,child);
        return query2(mid+1,r,child|1);
    }
    int query1(int l,int r,int node){
        if(VAL<tree[node]||r<P)return INT_MAX;
        if(P<=l)return query2(l,r,node);
        int mid=(l+r)>>1,child=node<<1;
        return min(query1(l,mid,child),query1(mid+1,r,child|1));
    }
    int query(int p,int val){
        P=p,VAL=val;
        int ans=query1(1,n,1);
        if(ans==INT_MAX)return -1;
        return ans;
    }
};

inline void solve(){
    int n,q;
    cin>>n>>q;
    segtree st(n);
    for(int i=0;i<q;i++){
        char ty;
        int v,p;
        cin>>ty>>v>>p;
        if(ty=='M'){
            st.update(p,v);
        }else{
            cout<<st.query(p,v)<<"\n";
        }
    }
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3416 KB Output is correct
2 Correct 2 ms 3416 KB Output is correct
3 Correct 3 ms 3416 KB Output is correct
4 Correct 69 ms 8016 KB Output is correct
5 Correct 95 ms 7656 KB Output is correct
6 Correct 92 ms 7668 KB Output is correct
7 Correct 102 ms 7912 KB Output is correct