Submission #342683

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
342683	2021-01-02T16:10:24 Z	saketh	Deda (COCI17_deda)	C++17	140 / 140	109 ms	6892 KB

deda

// segment_tree {{{
#include <vector>
#include <cassert>

template<typename T, typename AssociativeOperation>
struct segment_tree {
    int SZ;
    T identity;
    AssociativeOperation TT;
    std::vector<T> data;

    segment_tree() {}

    segment_tree(int _SZ, T _identity, AssociativeOperation _TT)
            : SZ(_SZ), identity(_identity), TT(_TT) {
        data.resize(2 * SZ, identity);
    }

    // Returns the value at index i
    const T& operator[](int i) const {
        assert(0 <= i && i < SZ);
        return data[SZ + i];
    }

    // Assigns fn(i) at index i for each i in [0, SZ)
    template<typename Function>
    void assign(Function fn) {
        for (int i = 0; i < SZ; i++)
            data[SZ + i] = fn(i);
        for (int i = SZ - 1; i; i--)
            data[i] = TT(data[2 * i], data[2 * i + 1]);
    }

    // Assigns v at index i
    void assign(int i, T v) {
        assert(0 <= i && i < SZ);
        data[i += SZ] = v;
        for (i /= 2; i; i /= 2)
            data[i] = TT(data[2 * i], data[2 * i + 1]);
    }

    // Returns the result of a left fold of the elements at indices in [first, last) over TT
    T accumulate(int first, int last) const {
        assert(0 <= first && last <= SZ);
        T left = identity, right = identity;
        for (first += SZ, last += SZ; first < last; first /= 2, last /= 2) {
            if (first & 1) left  = TT(left, data[first++]);
            if (last  & 1) right = TT(data[--last], right);
        }
        return TT(left, right);
    }
};
// }}}

// {{{ data_structures/segment_tree.cpp }}}

#include <cassert>

template<typename T, typename BinaryOperation>
struct searchable_segment_tree : segment_tree<T, BinaryOperation> {
    using segment_tree<T, BinaryOperation>::SZ;
    using segment_tree<T, BinaryOperation>::identity;
    using segment_tree<T, BinaryOperation>::TT;
    using segment_tree<T, BinaryOperation>::data;

    searchable_segment_tree() {}

    // Rounds up internal size to the nearest power of 2 to enable binary search
    searchable_segment_tree(int _SZ, T _identity, BinaryOperation _TT) :
        segment_tree<T, BinaryOperation>(1 << (32 - __builtin_clz(_SZ - 1)), _identity, _TT) {}

    /* Returns the smallest index "last" such that p(accumulate(first, last))
     * returns true. Returns SZ + 1 if no such index exists. Requires that
     * p(accumulate(first, last)) is non-decreasing as last increases.
     */
    template<typename Predicate>
    int binary_search(int first, Predicate p) const {
        assert(0 <= first && first <= SZ);

        if (p(identity))
            return first;

        first += SZ;

        T accumulator = identity;

        auto try_extend = [&](int bit) {
            assert(__builtin_ctz(first) >= bit);

            if (first + (1 << bit) > 2 * SZ)
                return false;

            T extended = TT(accumulator, data[first >> bit]);

            if (p(extended))
                return false;

            accumulator = extended;
            first += 1 << bit;
            return true;
        };

        int bit = 0;

        while (!(first & (1 << bit)) || try_extend(bit))
            bit++;

        while (--bit >= 0)
            try_extend(bit);

        return first - SZ + 1;
    }
};

#include <iostream>
#include <climits>
using namespace std;

// {{{ data_structures/searchable_segment_tree }}}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    auto smaller = [](int a, int b) { return min(a, b); };
    searchable_segment_tree<int, decltype(smaller)> sst(N, INT_MAX, smaller);

    for (int q = 0; q < Q; q++) {
        char op;
        int x, y;
        cin >> op >> x >> y;

        if (op == 'M') {
            sst.assign(y - 1, x);
        } else {
            int ans = sst.binary_search(y - 1, [&x](int v) { return v <= x; });
            cout << (ans > N ? -1 : ans) << "\n";
        }
    }

    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	2 ms	492 KB	Output is correct
4	Correct	109 ms	6892 KB	Output is correct
5	Correct	86 ms	5484 KB	Output is correct
6	Correct	98 ms	6764 KB	Output is correct
7	Correct	109 ms	6892 KB	Output is correct