oj.uz

답안 #954255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954255 2024-03-27T14:21:11 Z vjudge1 Deda (COCI17_deda) C++17
140 / 140
 101 ms 7848 KB 
#include <bits/stdc++.h>
using namespace std;
#define ishowspeed ios::sync_with_stdio(0),cin.tie(0);
#define int long long
#define MXN 200055
#define cl(x) (x<<1)
#define cr(x) (x<<1)+1
int seg[MXN*4+5],arr[MXN];
int searchb = 1e18;
int ansl = 1e18;
int query(int id,int l,int r,int sl,int sr){
    if(sl<=l&&r<=sr) {
        if(seg[id] > searchb) return seg[id];
        else{
            if(l == r) {
                ansl = min(ansl,l);
                return seg[id];
            }
        }
    }
    int mid=(l+r)>>1,res=1e18;
    if(sl<=mid){
        int x = query(cl(id),l,mid,sl,sr);
        res = min(res,x);
        if(x <= searchb) return res;
    } 
    if(mid<sr){
        int x = query(cr(id),mid+1,r,sl,sr);
        res = min(res,x);
    }  
    return res;
}
void pull(int id){
    seg[id] = min(seg[cl(id)] , seg[cr(id)]);
}
void update(int id,int l,int r,int x,int v){
    if(l==r){
        seg[id] = v;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid){
        update(cl(id),l,mid,x,v);    
    }
    if(mid<x){
        update(cr(id),mid+1,r,x,v);  
    }
    pull(id);
}
void build(int id,int l,int r){
    if(l==r){
        seg[id]=arr[l];
        return;
    }
    int mid=(l+r)>>1;
    build(cl(id),l,mid);
    build(cr(id),mid+1,r);
    pull(id);
}
signed main(){
    ishowspeed
    int n,q,x,L,R;
    cin >> n >> q;
    L = 1;
    R = n;
    for(int i = 1;i <= n;i++) arr[i] = 1e18;
    build(1,L,R);
    char o;
    int a,b;
    while(q--){
        cin >> o >> a >> b;
        if(o == 'M') update(1,L,R,b,a);
        else {
            searchb = a;
            ansl = 1e18;
            int rs = query(1,1,R,b,R);
            if(rs <= searchb) cout << ansl << '\n';
            else cout <<  "-1\n";
        }
    }
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:62:13: warning: unused variable 'x' [-Wunused-variable]
   62 |     int n,q,x,L,R;
      |             ^

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2552 KB Output is correct
4 Correct 101 ms 7848 KB Output is correct
5 Correct 76 ms 5456 KB Output is correct
6 Correct 79 ms 7508 KB Output is correct
7 Correct 84 ms 7764 KB Output is correct