Submission #871982

#	Time	Username	Problem	Language	Result	Execution time	Memory
871982		vjudge1	Deda (COCI17_deda)	C++17	100 / 140	119 ms	2220 KiB

deda

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

const int N = 200'000 + 7, SQ = 450;
int n, q, a[N], mn[SQ];

void read_input() {
    cin >> n >> q;
}

void change(int x, int y) {
    a[y] = x;
    mn[y / SQ] = min(mn[y / SQ], x);
}

int get(int x, int y) {
    for (int i = y; i / SQ <= y / SQ; i++)
        if (a[i] <= x)
            return i;
    for (int i = y / SQ + 1; i < SQ; i++)
        if (mn[i] <= x)
            for (int j = i * SQ; j < (i + 1) * SQ; j++)
                if (a[j] <= x)
                    return j;
    return -1;
}

void pre_process() {
    fill(a, a + N, 1e9 + 1);
    fill(mn, mn + SQ, 1e9 + 1);
}

void solve() {
    while (q--) {
        char c;
        int x, y;
        cin >> c >> x >> y;
        if (c == 'M')
            change(x, y - 1);
        else {
            int t = get(x, y - 1);
            cout << (t == -1 ? -1 : t + 1) << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    read_input();
    pre_process();
    solve();
}

• Subtask 1: 100 / 140