Submission #1284652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284652		supermani	Deda (COCI17_deda)	C++17	140 / 140	65 ms	5272 KiB

deda

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

const int INF = 1e9;

vector<int> t;
void build(const vector<int>& a, int v, int tl, int tr)
{
    if (tl==tr) t[v]=a[tl];
    else{
        int tm = (tl+tr)/2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = min(t[v*2], t[v*2+1]);
    }
}
int query(int v, int tl, int tr, int l, int r, int Y)
{
    if (l>r) return -1;
    if (t[v] > Y) return -1;
    if (tl == tr) return tl;
    int tm = (tl+tr)/2;
    if (l <= tm) {
        int left_res = query(v*2, tl, tm, l, min(r, tm), Y);
        if (left_res != -1) return left_res;
    }

    if (r > tm) {
        int right_res = query(v*2+1, tm+1, tr, max(l, tm+1), r, Y);
        if (right_res != -1) return right_res;
    }
    
    return -1;

}
void update(int v, int tl, int tr,int pos, int new_val)
{
    if (tl == tr) t[v] = new_val;
    else{
        int tm = (tl+tr)/2;
        if (pos<=tm) update(v*2, tl, tm, pos, new_val);
        else update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = min(t[v*2], t[v*2+1]);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    t.assign(4*N, 0);
    vector<int> a(N+1);
    for (int i=1; i<=N; i++) a[i] = INF;
    build(a,1,1,N);
    for (int i = 0; i<M; i++)
    {
        char op;
        cin >> op;
        if (op == 'M'){
            int X, A;
            cin >> X >> A;
            update(1,1,N,A,X);
        }
        else{
            int Y, B;
            cin >> Y >> B;
            cout << query(1, 1, N, B, N, Y) << '\n';
        }
    }
}

• Subtask 1: 140 / 140