제출 #659460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659460		vivo2006	Deda (COCI17_deda)	C++14	140 / 140	478 ms	10980 KiB

deda

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