Submission #446109

#	Time	Username	Problem	Language	Result	Execution time	Memory
446109		JovanB	Deda (COCI17_deda)	C++17	140 / 140	113 ms	6800 KiB

deda

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

using ll = long long;
using ld = long double;

const int INF = 1000000007;
const int MAXN = 200000;

int seg[4*MAXN+5];

void init(int node, int l, int r){
    if(l == r){
        seg[node] = INF;
        return;
    }
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
    seg[node] = min(seg[node*2], seg[node*2+1]);
}

void upd(int node, int l, int r, int x, int val){
    if(l == r){
        seg[node] = val;
        return;
    }
    int mid = (l+r)/2;
    if(x <= mid) upd(node*2, l, mid, x, val);
    else upd(node*2+1, mid+1, r, x, val);
    seg[node] = min(seg[node*2], seg[node*2+1]);
}

int query(int node, int l, int r, int b, int mx){
    if(seg[node] > mx) return -1;
    if(l == r) return l;
    int mid = (l+r)/2;
    if(b < mid){
        int k = query(node*2, l, mid, b, mx);
        if(k != -1) return k;
    }
    return query(node*2+1, mid+1, r, b, mx);
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, q;
    cin >> n >> q;
    init(1, 1, n);
    for(int i=1; i<=q; i++){
        char t;
        cin >> t;
        if(t == 'M'){
            int a, b;
            cin >> b >> a;
            upd(1, 1, n, a, b);
        }
        else{
            int y, b;
            cin >> y >> b;
            b--;
            cout << query(1, 1, n, b, y) << "\n";
        }
    }
    return 0;
}

• Subtask 1: 140 / 140