답안 #535487

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535487	2022-03-10T11:20:41 Z	LouayFarah	Deda (COCI17_deda)	C++14	140 / 140	107 ms	8888 KB

deda

#include "bits/stdc++.h"

using namespace std;

#define endl "\n"
#define ll long long int
#define pb push_back
#define mp make_pair
#define fi first
#define se second

const long long MOD = 1e9+7;
const long long INF = 1e18;

int nx[8] = {0, 0, -1, 1, 1, -1, -1, 1};
int ny[8] = {1, -1, 0, 0, 1, 1, -1, -1};

ll my_rand(ll l, ll r)
{
    srand(chrono::steady_clock::now().time_since_epoch().count());
    ll len = r-l+1;
    ll a = rand()%len;
    ll b = rand()%len;

    ll res = ((a%len) + (b%len))%len;

    if(res<l)
        res +=l;

    return res;
}


struct segtree
{
    ll size;
    ll INIT;
    vector<ll> values;

    void init(ll n)
    {
        size = 1;
        while(size<n)
            size*=2;

        INIT = 1e16;
        values.assign(2*size, INIT);
    }

    ll combine(ll a, ll b)
    {
        return min(a, b);
    }

    void change(ll i, ll v, ll lx, ll rx, ll x)
    {
        if(rx-lx<=1)
        {
            values[x] = v;
            return;
        }

        ll mid = (lx+rx)/2;

        if(i<mid)
            change(i, v, lx, mid, 2*x+1);
        else
            change(i, v, mid, rx, 2*x+2);

        values[x] = combine(values[2*x+1], values[2*x+2]);
    }

    ll op(ll l, ll y, ll lx, ll rx, ll x)
    {
        if(values[x]>y)
            return -1;
        if(rx<=l)
            return -1;

        if(rx-lx<=1)
        {
            return lx;
        }

        ll mid = (lx+rx)/2;

        ll res = op(l, y, lx, mid, 2*x+1);
        if(res==-1)
            res = op(l, y, mid, rx, 2*x+2);

        return res;
    }


    void change(ll i, ll v)
    {
        change(i, v, 0, size, 0);
    }

    ll op(ll l, ll y)
    {
        return op(l, y, 0, size, 0);
    }
};


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


    ll n, q;
    cin >> n >> q;

    segtree tree;
    tree.init(n+1);

    while(q--)
    {
        char c;
        cin >> c;

        if(c=='M')
        {
            ll x, a;
            cin >> x >> a;

            tree.change(a, x);
        }
        else
        {
            ll y, b;
            cin >> y >> b;

            ll res = tree.op(b, y);

            //if left<=y
            //else if right<=y
            //else return -1

            cout << res << endl;
        }
    }

    return 0;
}

Subtask #1

140.0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	2 ms	332 KB	Output is correct
4	Correct	84 ms	8888 KB	Output is correct
5	Correct	101 ms	6380 KB	Output is correct
6	Correct	88 ms	8624 KB	Output is correct
7	Correct	107 ms	8764 KB	Output is correct