제출 #1117373

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117373		danglayloi1	Deda (COCI17_deda)	C++17	140 / 140	75 ms	8008 KiB

deda

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=2e5+5;
int n, q, nod[nx<<2];
void update(int id, int l, int r, int p, int val)
{
    if(l>p || r<p)
        return;
    if(l==r)
        return void(nod[id]=val);
    int mid=(l+r)>>1;
    update(id<<1, l, mid, p, val);
    update(id<<1|1, mid+1, r, p, val);
    nod[id]=min(nod[id<<1], nod[id<<1|1]);
}
int find(int id, int l, int r, int lim, int val)
{
    if(nod[id]>val)
        return -1;
    if(r<lim)
        return -1;
    if(l==r)
        return l;
    int mid=(l+r)>>1;
    int res=-1;
    if(nod[id<<1]<=val)
        res=find(id<<1, l, mid, lim, val);
    if(res==-1)
        res=find(id<<1|1, mid+1, r, lim, val);
    return res;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>q;
    memset(nod, 0x3f, sizeof(nod));
    while(q--)
    {
        char c;
        int x, y;
        cin>>c>>x>>y;
        if(c=='M')
            update(1, 1, n, y, x);
        else cout<<find(1, 1, n, y, x)<<'\n';
    }
}

• Subtask 1: 140 / 140