Submission #1303700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303700		itzmanu	Deda (COCI17_deda)	C++20	140 / 140	63 ms	5424 KiB

deda

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

#define nitro ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
#define int long long 
#define vi vector<long long> 
#define spc " " 
#define yes "YES" 
#define no "NO"
#define endl "\n" 
const int INF = 1e18;
const int maxn = 200005; 
const int mod = 32768; 

int tree[4 * maxn];

void build(int node, int start, int end) {
    if (start == end) {
        tree[node] = INF;
    } else {
        int mid = (start + end) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        tree[node] = min(tree[2 * node], tree[2 * node + 1]);
    }
}

void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        tree[node] = val;
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid) update(2 * node, start, mid, idx, val);
    else update(2 * node + 1, mid + 1, end, idx, val);
    
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}

int query(int node, int start, int end, int b, int y) {
    if (tree[node] > y || end < b) return -1;

    if (start == end) return start;

    int mid = (start + end) / 2;
    int res = -1;
    
    if (mid >= b) {
        res = query(2 * node, start, mid, b, y);
    }

    if (res != -1) return res;
    
    return query(2 * node + 1, mid + 1, end, b, y);
}
void solve() {
    int n, q;
    cin >> n >> q;

    build(1, 1, n);

    while (q--) {
        char type;
        int a, b;
        cin >> type >> a >> b;

        if (type == 'M') {
            update(1, 1, n, b, a); 
        } else {
            cout << query(1, 1, n, b, a) << "\n";
        }
    }
}

signed main() { 
    nitro 
    int t = 1; 
    //cin >> t;
    for(int i = 1; i <= t; i++) { 
        solve(); 
    } 
    return 0; 
}

• Subtask 1: 140 / 140