oj.uz

Submission #954351

# Submission time Handle Problem Language Result Execution time Memory
954351 2024-03-27T16:25:48 Z vjudge1 Deda (COCI17_deda) C++17
80 / 140
 1000 ms 3756 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(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;
        }
        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
80.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 348 KB Output is correct
4 Correct 269 ms 3756 KB Output is correct
5 Execution timed out 1058 ms 3028 KB Time limit exceeded
6 Execution timed out 1042 ms 3164 KB Time limit exceeded
7 Execution timed out 1057 ms 3024 KB Time limit exceeded