Submission #1138715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138715		m_kulas	Deda (COCI17_deda)	C++20	140 / 140	76 ms	17736 KiB

deda

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
#define pb push_back

const int N = 200'100;
constexpr int base = 1 << 20;

LL tree[2*base];

void build(int v, int a, int b)
{
    if(a==b)
        tree[v] = LLONG_MAX;
    else
    {
        int mid = (a+b)/2;
        build(v*2, a, mid);
        build(v*2+1, mid+1, b);
        tree[v] = LLONG_MAX;
    }
}

void update(int v, int a, int b, int pos, int val)
{
    if(a==b)
        tree[v] = val;
    else
    {
        int mid = (a+b)/2;
        if(pos <= mid) update(v*2, a, mid, pos, val);
        else update(v*2+1, mid+1, b, pos, val);

        tree[v] = min(tree[v*2], tree[v*2+1]);
    }
}
int p, k, val;
int get_first(int v, int a, int b)
{
   // cout << v << " " << a << " " << b << " : " << tree[v] << endl;
    if(a > k || b < p)
        return -1;

    if(tree[v] > val || tree[v] == LLONG_MAX)
        return -1;

    if(a==b)
        return a;

    int mid = (a+b)/2;
    int left = get_first(2*v, a, mid);
    if(left != -1) return left;
    return get_first(2*v+1, mid+1, b);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    build(1, 1, base-1);
    while(m--)
    {
        char t; int a, b;
        cin >> t >> a >> b;

        if(t == 'M')
        {
            update(1, 1, base-1, b, a);
        }
        else
        {
            p = b, k = n, val = a;
            cout << get_first(1, 1, base-1) << "\n";
        }
    }


}

• Subtask 1: 140 / 140