oj.uz

Submission #954353

# Submission time Handle Problem Language Result Execution time Memory
954353 2024-03-27T16:30:54 Z vjudge1 Deda (COCI17_deda) C++17
140 / 140
 83 ms 3676 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
#define N 200005
#define cl(x) (x<<1)
#define cr(x) (x<<1)+1
#define inf (int)1e9
using namespace std;

char c;
int n, m, x, y, ans;
int seg[4*N];

void build(int id, int l, int r){
    if(l==r){
        seg[id] = inf;
        return;
    }
    int mid = (l+r)>>1;
    build(cl(id), l, mid);
    build(cr(id), mid+1, r);
    seg[id] = inf;
}
void query(int id, int l, int r, int station, int student){
    if(ans!=inf) return;
    if(r<student) return;
    if(l==r && seg[id]<=station && l>=student){
        ans = min(ans, l);
        return;
    }
    else if(l==r) return;

    if(seg[id]<=station){
        int mid = (l+r)>>1;
        if(student > mid){
            query(cr(id), mid+1, r, station, student);
            return;
        }
        if(seg[cl(id)]<=station) query(cl(id), l, mid, station, student);
        if(seg[cr(id)]<=station) query(cr(id), mid+1, r, station, student);
    }
}
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);
    }
    else{
        update(cr(id), mid+1, r, x, v);
    }
    seg[id] = min(seg[cl(id)], seg[cr(id)]);
}


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    build(1, 1, n);
    while(m--){
        cin >> c >> x >> y;
        if(c=='M'){
            update(1, 1, n, y, x);
        }
        else{
            ans = inf;
            query(1, 1, n, x, y);
            if(ans==inf) ans = -1;
            cout << ans << '\n';
        }
    }


    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 78 ms 3676 KB Output is correct
5 Correct 81 ms 3360 KB Output is correct
6 Correct 83 ms 3408 KB Output is correct
7 Correct 81 ms 3548 KB Output is correct