oj.uz

Submission #872028

# Submission time Handle Problem Language Result Execution time Memory
872028 2023-11-12T06:46:02 Z vjudge1 Deda (COCI17_deda) C++17
100 / 140
 1000 ms 2128 KB 
#include <bits/stdc++.h>
using namespace std;

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

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

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

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

int get(int y, int b) {
    for (int i = b; (i / SQ) <= ((n - 1) / SQ) /*(b / SQ)*/; i++)
        if (s[i] <= y)
            return i;

/*    for (int i = b / SQ + 1; i <= (n - 1) / SQ; i++)
        if (mn[i] <= y) {
            for (int j = i * SQ; j < min((i + 1) * SQ, n); j++)
                if (s[j] <= y)
                    return j;
            assert(false);
        }*/
    
    return -1;
}

void solve() {
    while (q--) {
        char c;
        int x, y;
        cin >> c >> x >> y;

        if (c == 'M') {
            change(x, y - 1);
        } else if (c == 'D') {
            int t = get(x, y - 1);
            cout << (t == -1 ? -1 : t + 1) << '\n';
        } else {
            assert(false);
        }
    }
}

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

Subtask #1
100.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct
4 Execution timed out 1037 ms 1240 KB Time limit exceeded
5 Correct 372 ms 1876 KB Output is correct
6 Correct 673 ms 2128 KB Output is correct
7 Execution timed out 1058 ms 2080 KB Time limit exceeded