Submission #572915

#	Time	Username	Problem	Language	Result	Execution time	Memory
572915		ddy888	Deda (COCI17_deda)	C++17	140 / 140	734 ms	7968 KiB

deda

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int INF = 1e9;

int n, q;

struct SegTree {
    vector<int> t;
    void init(int sz) {t.resize(sz * 4, INF);}
    void set(int p, int v, int id = 1, int lx = 1, int rx = n) {
        if (lx == rx ) {
            t[id] = v;
            return;
        }
        int mid = (lx + rx) >> 1;
        if (p <= mid) set(p, v, 2*id, lx, mid);
        else set(p, v, 2*id+1, mid+1, rx);
        t[id] = min(t[2*id], t[2*id+1]);
    }
    int get(int qs, int qe, int id = 1, int lx = 1, int rx = n) {
        if (qe < lx || qs > rx) return INF;
        if (qs <= lx && qe >= rx) return t[id];
        int mid = (lx + rx) >> 1;
        return min(get(qs, qe, 2*id, lx, mid), get(qs, qe, 2*id+1, mid+1, rx));
    }
};

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 

    cin >> n >> q;
    SegTree st; st.init(n); 
    while (q--) {
        char op; cin >> op;
        if (op == 'M') {
            int x, a; cin >> x >> a;
            st.set(a, x);
        } else {
            int y, b; cin >> y >> b;

            int lo = b - 1, hi = n + 1;
            while (lo + 1 < hi) {
                int mid = (lo + hi) >> 1;
                if (st.get(b, mid) <= y) hi = mid;
                else lo = mid;       
            }
            cout << (hi == n+1 ? -1 : hi) << '\n';
        }
    }

    return 0;
}

• Subtask 1: 140 / 140