oj.uz

Submission #954349

# Submission time Handle Problem Language Result Execution time Memory
954349 2024-03-27T16:17:46 Z vjudge1 Deda (COCI17_deda) C++17
60 / 140
 5 ms 1628 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[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(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;
        query(cl(id), l, mid, station, student);
        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
60.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 5 ms 480 KB Output is correct
4 Runtime error 1 ms 604 KB Execution killed with signal 11
5 Runtime error 1 ms 1628 KB Execution killed with signal 11
6 Runtime error 1 ms 604 KB Execution killed with signal 11
7 Runtime error 1 ms 604 KB Execution killed with signal 11