oj.uz

Submission #866819

# Submission time Handle Problem Language Result Execution time Memory
866819 2023-10-27T08:10:05 Z RaulAndrei01 Deda (COCI17_deda) C++17
140 / 140
 378 ms 7252 KB 
#include <vector>
#include <iostream>

using namespace std;
const int NMAX = 2e5;
const int INF = 1e9 + 10;

struct AINT {
    vector<int> aint;
    int n , offset;

    AINT (int _n)
    {
        n = _n;
        offset = 1;
        while (offset < n) offset <<= 1;
        aint.resize(2 * offset , INF);
    }

    void update (int pos , int val)
    {
        _update (1 , 1 , offset , pos , val);
    }

    void _update (int nod , int l , int r , int pos , int val)
    {
        if (l == r)
        {
            if (l == pos) aint[nod] = val;
            return;
        }
        if (pos < l || r < pos) return;
        int mid = (l + r) / 2;
        _update(2 * nod , l , mid, pos, val);
        _update(2*nod+1, mid+1, r, pos, val);
        aint[nod] = merge (aint[2*nod] , aint[2*nod+1]);
    }

    int merge (int nod1, int nod2)
    {
        return min(nod1, nod2);
    }

    int bs (int pos , int val)
    {
        int nod = offset + pos - 1;
        while (aint[nod] > val && nod > 0)
        {
            if (nod == 1) nod = 0;
            else if (nod%2 == 1 && (nod & (nod+1)) == 0) {
                nod = 0;
            }
            else if (nod % 2 == 1) nod = nod / 2 + 1;
            else nod /= 2;
        }
    //    cout << nod << '\n';
        if (nod == 0) return -1;
        while (nod < offset)
        {
            if (aint[2*nod] > val) nod = 2 * nod + 1;
            else nod = 2 * nod;
        }
        return nod - offset + 1;
    }

};

int main ()
{
    int n , q; cin >> n >> q;
    AINT aint(n);
    while (q--)
    {
        char c; cin >> c;
        if (c == 'M')
        {
            int x, a; cin >> x >> a;
            aint.update(a, x);
        }
        else {
            int y, b; cin >> y >> b;
            cout << aint.bs(b, y) << '\n';
        }
    }
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 7 ms 508 KB Output is correct
4 Correct 378 ms 7096 KB Output is correct
5 Correct 289 ms 5456 KB Output is correct
6 Correct 326 ms 7252 KB Output is correct
7 Correct 322 ms 6788 KB Output is correct