oj.uz

Submission #872000

# Submission time Handle Problem Language Result Execution time Memory
872000 2023-11-12T06:10:01 Z vjudge1 Deda (COCI17_deda) C++17
140 / 140
 149 ms 2132 KB 
/*              IN THE NAME OF GOD              */
// Oh, let the bullets fly, oh, let them rain
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200'000, sq = 450, inf = 1'000'000'010;

int out[MAXN + 10], mn_sq[sq + 10], n, q;

void input();
void solve();
void query1(int x, int a);
int query2(int y, int b);

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

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

void solve() {
    for (int i = 0; i < n; i++)
        out[i] = inf;
    for (int i = 0; i < sq; i++)
        mn_sq[i] = inf;
    while (q--) {
        char type;
        int k1, k2;
        cin >> type >> k1 >> k2;
        k2--;
        if (type == 'M')
            query1(k1, k2);
        else
            cout << query2(k1, k2) << '\n';
    }
}

void query1(int x, int a) {
    mn_sq[a / sq] = min(mn_sq[a / sq], x);
    out[a] = x;
}

int query2(int y, int b) {
    int tmp = inf, ptr1 = b;
    do {
        tmp = min(tmp, out[ptr1]);
        if (tmp <= y)
            return ptr1 + 1;
        ptr1++;
    } while (ptr1 % sq && ptr1 < n);
    int prv = tmp;
    for (int i = b / sq + 1; i <= n / sq; i++) {
        tmp = min(tmp, mn_sq[i]);
        if (tmp <= y) {
            int res = prv;
            for (int j = i * sq; j < min((i + 1) * sq, n); j++) {
                res = min(res, out[j]);
                if (res <= y)
                    return j + 1;
            }
        }
        prv = tmp;
    }
    return -1;
}

Subtask #1
140.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 1 ms 348 KB Output is correct
4 Correct 149 ms 2132 KB Output is correct
5 Correct 62 ms 1372 KB Output is correct
6 Correct 73 ms 1940 KB Output is correct
7 Correct 84 ms 2128 KB Output is correct