Submission #883293

#	Time	Username	Problem	Language	Result	Execution time	Memory
883293		vjudge1	Deda (COCI17_deda)	C++17	140 / 140	75 ms	8044 KiB

deda

#include <bits/stdc++.h>
using namespace std;

const int N = 200'000;
const int INF = 2'000'000'000;

int n, q;
int mn[4 * N + 10];

int get(int st, int en, int y, int id = 1, int l = 1, int r = n + 1) {
    if (en <= l || r <= st || y < mn[id])
        return -1;
    if (l + 1 == r)
        return l;
    int mid = (l + r) >> 1;
    int case1 = get(st, en, y, id << 1, l, mid);
    if (case1 != -1)
        return case1;
    return get(st, en, y, id << 1 | 1, mid, r);
}

void update(int idx, int val, int id = 1, int l = 1, int r = n + 1) {
    if (idx < l || r <= idx)
        return;
    if (l + 1 == r) {
        mn[id] = val;
        return;
    }
    int mid = (l + r) >> 1;
    update(idx, val, id << 1, l, mid);
    update(idx, val, id << 1 | 1, mid, r);
    mn[id] = min(mn[id << 1], mn[id << 1 | 1]);
}

void init() {
    fill(mn + 1, mn + 4 * n + 10, INF);
}

void query() {
    char type;
    cin >> type;
    int a, b;
    cin >> a >> b;
    if (type == 'M')
        update(b, a);
    else
        cout << get(b, n + 1, a) << '\n';
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    init();
    while (q--)
        query();
    cout.flush();
    return 0;
}

• Subtask 1: 140 / 140