oj.uz

답안 #926818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
926818 2024-02-13T20:26:41 Z Kihihihi Deda (COCI17_deda) C++17
140 / 140
 349 ms 8040 KB 
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e9;

struct segtree
{
    int n;
    vector<int> t;

    segtree(int in)
    {
        n = in;
        t.resize(n * 4, INF);
    }
    
    void upd_elem(int v, int tl, int tr, int a, int x)
    {
        if (tl == tr)
        {
            t[v] = min(t[v], x);
            return;
        }

        int tm = (tl + tr) / 2;
        if (a <= tm)
        {
            upd_elem(v * 2 + 1, tl, tm, a, x);
        }
        else
        {
            upd_elem(v * 2 + 2, tm + 1, tr, a, x);
        }
        t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
    }

    void upd(int a, int x)
    {
        upd_elem(0, 0, n - 1, a, x);
    }
    
    int get_elem(int v, int tl, int tr, int b, int y)
    {
        if (tr < b || t[v] > y)
        {
            return -1;
        }
        if (tl == tr)
        {
            return tl;
        }

        int tm = (tl + tr) / 2;
        int resl = get_elem(v * 2 + 1, tl, tm, b, y);
        if (resl != -1)
        {
            return resl;
        }
        return get_elem(v * 2 + 2, tm + 1, tr, b, y);
    }

    int get(int b, int y)
    {
        return get_elem(0, 0, n - 1, b, y);
    }
};

int main()
{
    int n, q;
    cin >> n >> q;
    segtree sgt(n);
    while (q--)
    {
        char qt;
        cin >> qt;
        if (qt == 'M')
        {
            int x, a;
            cin >> x >> a;
            a--;
            sgt.upd(a, x);
        }
        else
        {
            int y, b;
            cin >> y >> b;
            b--;

            int res = sgt.get(b, y);
            cout << (res == -1 ? -1 : res + 1) << "\n";
        }
    }

    return 0;
}

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 7 ms 348 KB Output is correct
4 Correct 349 ms 8040 KB Output is correct
5 Correct 296 ms 5908 KB Output is correct
6 Correct 325 ms 6928 KB Output is correct
7 Correct 337 ms 7992 KB Output is correct