oj.uz

Submission #446109

# Submission time Handle Problem Language Result Execution time Memory
446109 2021-07-21T00:07:02 Z JovanB Deda (COCI17_deda) C++17
140 / 140
 113 ms 6800 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 99 ms 6800 KB Output is correct
5 Correct 112 ms 5308 KB Output is correct
6 Correct 109 ms 6612 KB Output is correct
7 Correct 113 ms 6680 KB Output is correct