oj.uz

Submission #572915

# Submission time Handle Problem Language Result Execution time Memory
572915 2022-06-05T13:32:28 Z ddy888 Deda (COCI17_deda) C++17
140 / 140
 734 ms 7968 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 734 ms 7968 KB Output is correct
5 Correct 438 ms 5892 KB Output is correct
6 Correct 523 ms 6932 KB Output is correct
7 Correct 574 ms 7896 KB Output is correct