제출 #926818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
926818		Kihihihi	Deda (COCI17_deda)	C++17	140 / 140	349 ms	8040 KiB

deda

#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 / 140