# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
484809 | Felerius | Deda (COCI17_deda) | C++17 | 80 ms | 3640 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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';
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |