oj.uz

Submission #659460

# Submission time Handle Problem Language Result Execution time Memory
659460 2022-11-17T20:23:34 Z vivo2006 Deda (COCI17_deda) C++14
140 / 140
 478 ms 10980 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, q, val, a, b;
int tree[800008];
char type;
void update(int ind, int index, int l, int r)
{
    //cout<<ind<<" "<<l<<" "<<r<<endl;
    if(l == r)
    {
        tree[ind] = a;
         //cout<<tree[ind]<<endl;
        return;
    }
    int mid = (l + r) / 2;
    if(index <= mid) update(ind * 2 + 1, index, l, mid);
    else update(ind * 2 + 2, index, mid + 1, r);
    tree[ind] = min(tree[ind * 2 + 1], tree[ind * 2 + 2]);
    //cout<<tree[ind]<<endl;
}
int bsa(int ind, int l, int r)
{
    //cout<<l<<" "<<r<<": "<<tree[ind]<<endl;
    if(tree[ind] > a) return 1000000001;
    if(l == r) return l;
    int mid = (l + r) / 2;
    if(tree[ind * 2 + 1] <= a) return bsa(ind * 2 + 1, l, mid);
    if(tree[ind * 2 + 2] <= a) return bsa(ind * 2 + 2, mid + 1, r);
    return 1000000001;
}
int query(int ind, int l, int r, int curL, int curR)
{
     if(curL > r || curR < l) return 1000000001;
     if(curL >= l && curR <= r)
     {
         //cout<<"Binary search for: "<<ind<<" "<<curL<<" "<<curR<<endl;
         return bsa(ind, curL, curR);
     }
     int mid = (curL + curR) / 2;
     return min(query(ind * 2 + 2, l, r, mid + 1, curR), query(ind * 2 + 1, l, r, curL, mid));
}
signed main()
{
    cin>>n>>q;
    for(int i = 0; i < 800008; i ++) tree[i] = 1000000001;
    for(int i = 0; i < q; i ++)
    {
        cin>>type>>a>>b;
        if(type == 'M')
        {
            update(0, b, 1, 200001);
        }
        else
        {
            int res = query(0, b, 200001, 1, 200001);
            if(res != 1000000001)cout<<res<<'\n';
            else cout<<"-1\n";
        }
    }
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 4 ms 6452 KB Output is correct
3 Correct 11 ms 6612 KB Output is correct
4 Correct 478 ms 10980 KB Output is correct
5 Correct 403 ms 10584 KB Output is correct
6 Correct 403 ms 10848 KB Output is correct
7 Correct 445 ms 10892 KB Output is correct