Submission #954351

#	Time	Username	Problem	Language	Result	Execution time	Memory
954351		vjudge1	Deda (COCI17_deda)	C++17	80 / 140	1058 ms	3756 KiB

deda

#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 / 140