Submission #1083198

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1083198	2024-09-02T17:53:55 Z	mihneacazan	Deda (COCI17_deda)	C++17	140 / 140	366 ms	8836 KB

deda

#include <bits/stdc++.h>

using namespace std;

template<typename T>
class SegTree {
private:
    int n;  // Size of the input array
    std::vector<T> t;  // Segment tree array
    std::function<T(T, T)> combine;  // Function to combine two nodes
    //std::vector<bool> marked;
    //std::vector<int> lazy;

    /*void assign_push(int v) {
        if (marked[v]) {
            t[v*2] = t[v*2+1] = t[v];
            marked[v*2] = marked[v*2+1] = true;
            marked[v] = false;
        }
    }

    void addition_push(int v) {
        t[v*2] += lazy[v];
        lazy[v*2] += lazy[v];
        t[v*2+1] += lazy[v];
        lazy[v*2+1] += lazy[v];
        lazy[v] = 0;
    }*/

    void build(const std::vector<T>& 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] = combine(t[v*2], t[v*2+1]);
        }
    }

    T query_non_lazy(int v, int tl, int tr, int l, int r, int y) {
        // cout << v << " " << tl << " " << tr << " " << l << " " << r << " " << y << " " << t[v] << "\n";
        if (tl > r || tr < l || t[v] > y) return -1;
        if (tl == tr) {
            return tl;
        }
        int tm = (tl + tr) / 2;
        int left = query_non_lazy(2*v, tl, tm, l, r, y);
        if (left != -1) return left;
        return query_non_lazy(2*v+1, tm+1, tr, l, r, y);
    }

    void non_lazy_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)
                non_lazy_update(v*2, tl, tm, pos, new_val);
            else
                non_lazy_update(v*2+1, tm+1, tr, pos, new_val);
            t[v] = combine(t[v*2], t[v*2+1]);
        }
    }

public:
    // Constructor to initialize the segment tree
    SegTree(const std::vector<T>& a, std::function<T(T, T)> combineFunc) {
        n = a.size();
        t.resize(4 * n);
        // marked.resize(4 * n);
        // lazy.resize(4 * n);
        combine = combineFunc;
        build(a, 1, 0, n - 1);
    }

    // Point update function
    void SetPoint(int pos, T new_val) {
        non_lazy_update(1, 0, n - 1, pos, new_val);
    }
    T query(int y, int b) {
        return query_non_lazy(1, 0, n - 1, b, n, y);
    }
};

int combine(int x, int y)
{
    return min(x, y);
}

int main()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n, INT_MAX);
    SegTree<int> seg(a, combine);
    while (q--) {
        char c;
        cin >> c;
        if (c == 'M') {
            int X, A;
            cin >> X >> A;
            A--;
            a[A] = X;
            seg.SetPoint(A, a[A]);
        } else {
            int Y, B;
            cin >> Y >> B;
            B--;
            int k = seg.query(Y, B);
            if (k == -1) cout << "-1\n";
            else cout << k + 1 << "\n";
        }
    }
    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	7 ms	348 KB	Output is correct
4	Correct	357 ms	8836 KB	Output is correct
5	Correct	265 ms	6228 KB	Output is correct
6	Correct	296 ms	7508 KB	Output is correct
7	Correct	366 ms	8784 KB	Output is correct