Submission #484809

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
484809	2021-11-05T14:30:01 Z	Felerius	Deda (COCI17_deda)	C++17	140 / 140	80 ms	3640 KB

deda

#pragma GCC optimize("fast-math")
// begin "cp-lib/prelude.hpp"
#include <bits/stdc++.h>
#ifdef LOCAL
#  include <dbg.h>
#else
#  define dbg(...) do {} while (0)
#endif

#define cp_lib_4th(_1, _2, _3, x, ...)  x
#define cp_lib_rep(i, l, r)             for (int i = (l); (i) < (r); ++(i))
#define cp_lib_rep0(i, r)               cp_lib_rep(i, 0, r)
#define rep(...)                        cp_lib_4th(__VA_ARGS__, cp_lib_rep, cp_lib_rep0, _)(__VA_ARGS__)
#define cp_lib_repr(i, r, l, ...)       for (int i = (r); (i) >= (l); --(i))
#define repr(...)                       cp_lib_repr(__VA_ARGS__, 0)
#define all(a)                          ::begin(a),::end(a)
#define trav(a, b)                      for (auto&& a : (b))

using namespace std;
using ll = long long;
using ld = long double;
[[maybe_unused]] static constexpr int INF = int(1e9 + 5);
[[maybe_unused]] static constexpr ll INFL = ll(INF) * INF;
template <class C> int sz(const C& c) { return int(::size(c)); }
// end "cp-lib/prelude.hpp"
// #include "cp-lib/io.hpp"

template <class Data, class Combine>
class SegmentTree {
    int n;
    const Data identity;
    Combine combine;
    vector<Data> tree;

    void recalc(int i) { tree[i] = combine(tree[i << 1], tree[(i << 1) | 1]); }
    void rebuild(int i) { for (i >>= 1; i; i >>= 1) recalc(i); }

    template <class Pred>
    int lower_bound_full(int v, Data prefix, Pred&& pred) {
        while (v < n)
            if (auto prefix2 = identity; !pred(prefix2 = combine(prefix, tree[v <<= 1])))
                ++v, prefix = prefix2;
        return v - n;
    }

 public:
    SegmentTree(int n_, Data identity_, Combine combine_)
        : n(n_), identity(identity_), combine(move(combine_)), tree(2 * n, identity) {}

    template <class It, class ItEnd>
    SegmentTree(It it, It it_end, Data identity_, Combine combine_)
        : SegmentTree(int(it_end - it), identity_, move(combine_)) {
        copy(it, it_end, begin(tree) + n);
        build();
    }

    Data& root() { return tree[1]; }
    Data& leaf(int i) { return tree[i + n]; }

    void build() { repr(i, n - 1, 1) recalc(i); }

    Data query(int l, int r) {
        auto left = identity, right = identity;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) left = combine(left, tree[l++]);
            if (r & 1) right = combine(right, tree[--r]);
        }
        return combine(left, right);
    }

    template <class Update>
    void point_update(int i, Update&& update) {
        update(tree[i + n]);
        rebuild(i + n);
    }

    template <class Pred>
    int lower_bound(int l, int r, Pred&& pred) {
        auto prefix = identity;
        array<int, 32> nodes;
        int cnt = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (auto old_prefix = prefix; l & 1 && pred(prefix = combine(prefix, tree[l++])))
                return lower_bound_full(l - 1, old_prefix, forward<Pred>(pred));
            if (r & 1)
                nodes[cnt++] = --r;
        }
        repr(i, cnt - 1)
            if (auto old_prefix = prefix; pred(prefix = combine(prefix, tree[nodes[i]])))
                return lower_bound_full(nodes[i], old_prefix, forward<Pred>(pred));
        return n;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(false);
    // int n, q; read(n, q);
    int n, q; cin >> n >> q;
    SegmentTree seg(n, INF, [](int a, int b) { return min(a, b); });
    vector vals(n, INF);
    while (q--) {
        // char ty; int a, i; read(ty, a, i); --i;
        char ty; int a, i; cin >> ty >> a >> i; --i;
        if (ty == 'M')
            seg.point_update(i, [&](int& val) { val = a; });
        else {
            int ans = seg.lower_bound(i, n, [&](int mn) { return mn <= a; });
            // println(ans == n ? -1 : ans + 1);
            cout << (ans == n ? -1 : ans + 1) << '\n';
        }
    }
}

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	2 ms	332 KB	Output is correct
4	Correct	80 ms	3632 KB	Output is correct
5	Correct	80 ms	2184 KB	Output is correct
6	Correct	68 ms	2980 KB	Output is correct
7	Correct	72 ms	3640 KB	Output is correct