제출 #1342825

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1342825		UVince	Deda (COCI17_deda)	C++20	140 / 140	321 ms	4560 KiB

deda

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

const ll mod=1e9+7;
const ll inf=1e10;

const int maxn=2e5+1;
int n,q;

ll tree[2*maxn];

void upd(int idx, ll x){
    for (tree[idx+=n]=x; idx>1; idx>>=1) tree[idx>>1] = min(tree[idx], tree[idx^1]);
}

ll get(int l, int r){
    ll res = inf;
    for (l+=n, r+=n; l<r; l>>=1, r>>=1){
        if (l&1) res=min(res, tree[l++]);
        if (r&1) res=min(res, tree[--r]);
    }
    return res;
}

void solve() {
    cin>>n>>q;
    for (int i=0;i<n;i++) upd(i, inf);

    while (q--){
        char c; ll a; int b;
        cin>>c>>a>>b;
        if (c=='M'){
            upd(b-1, a);
        }
        else {
            int l=b-1, r=n+1;
            while (l+1<r){
                int m = (l+r)/2;
                ll res = get(b-1, m);
                if (res<=a) r=m;
                else l=m;
            }
            if (r==n+1) cout<<"-1\n";
            else cout<<r<<"\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) solve();
}

• Subtask 1: 140 / 140