제출 #979445

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
979445		vjudge1	Deda (COCI17_deda)	C++17	140 / 140	672 ms	11140 KiB

deda

// clang-format off
#include <bits/stdc++.h>
using namespace std;

// --------------------------- Defines -------------------------------------  //
template<typename A, typename B> 
ostream& operator<<(ostream &os, const pair<A, B> &p) { 
    return os << '(' << p.first << ", " << p.second << ')'; 
}

template <typename Tc,
          typename T = typename enable_if<!is_same<Tc, string>::value,
                                          typename Tc::value_type>::type>
ostream &operator<<(ostream &os, const Tc &v) {
    os << '{';
    for (const T &x : v) os << x << ',';
    return os << '}';
}

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }

#ifdef DEBUG
    #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
    #define dbg(...)
#endif

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define forn(i, n) for(int i = 0; i < n; i++)
#define readvec(vec) for(auto& it : vec) cin >> it;
#define MOD(n) ( ( ((n) % mod) + mod ) % mod)

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vp;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds ;

typedef tree <
    int, // Key
    null_type, // Value
    less <int>, // Comp
    rb_tree_tag,
    tree_order_statistics_node_update
> ordered_set;

// --------------------------- Constants ----------------------------------- //
const ll LN = 0, 
         LM = 0, 
         mod = (ll)(1e9) + 7;
// ------------------------- Your code ---------------------------------- //
// clang-format on

vl st;

ll update(int node, int l, int r, int pos, int x) {
    if (pos < l || r < pos) return st[node];
    if (l == r) return st[node] = x;
    int m = (l + r) / 2;
    return st[node] = min(update(node * 2, l, m, pos, x), update(node*2 + 1, m + 1, r, pos, x));
}

ll query(int node, int l, int r, int lq, int rq) {
    if (lq <= l && r <= rq) return st[node];
    if (r < lq || rq < l) return 1e9 + 1;
    int m = (l + r) / 2;
    return min(query(node * 2, l, m, lq, rq), query(node * 2 + 1, m + 1, r, lq, rq));
}

void Solve() {
    int N, Q;
    cin >> N >> Q;
    st.resize(4 * N, 1e9 + 1);
    while (Q--) {
        char aux; cin >> aux;
        if (aux == 'M') {
            int x, a;
            cin >> x >> a; // a is pos, x stop
            update(1, 1, N, a, x);
        } else {
            int y, b;
            cin >> y >> b;
            int l = b, r = N;
            if (query(1, 1, N, b, N) > y) {
                cout << -1 << '\n';
                continue;
            }
            while (l != r) {
                int m = (l + r) / 2;
                if (query(1, 1, N, b, m) <= y) r = m;
                else l = m + 1;
            }
            cout << l << '\n';
        }
    }
}

// clang-format off
// --------------------------------------------------------------------- //
int main() {
    #ifdef DEBUG
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #else
        ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int Tc = 1;
    //cin >> Tc;

    forn(i, Tc)
        Solve();

    return 0;
}

• Subtask 1: 140 / 140