Submission #792398

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
792398	2023-07-25T04:07:44 Z	Nhoksocqt1	Deda (COCI17_deda)	C++17	140 / 140	72 ms	7548 KB

deda

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 200005;

int posInTree[MAXN], seg[4 * MAXN], nArr, numQuery;

void build(int id, int l, int r) {
    seg[id] = 1e9+7;
    if(l == r) {
        posInTree[l] = id;
        return;
    }

    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
}

void update(int pos, int val) {
    int id(posInTree[pos]);

    seg[id] = val;
    while(id > 1) {
        id >>= 1;
        seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
    }
}

int walkOnSeg(int id, int l, int r, int u, int v, int k) {
    if(v < l || u > r || seg[id] > k)
        return -1;

    if(u <= l && r <= v) {
        while(l < r) {
            int mid = (l + r) >> 1;
            if(seg[id << 1] <= k) {
                id = id << 1;
                r = mid;
            } else {
                id = id << 1 | 1;
                l = mid + 1;
            }
        }

        return l;
    }

    int mid = (l + r) >> 1;
    int qr = walkOnSeg(id << 1, l, mid, u, v, k);
    if(qr != -1)
        return qr;

    return walkOnSeg(id << 1 | 1, mid + 1, r, u, v, k);
}

void process() {
    cin >> nArr >> numQuery;

    build(1, 1, nArr);
    for (int t = 0; t < numQuery; ++t) {
        char c;
        int u, v;
        cin >> c >> u >> v;
        if(c == 'M') {
            update(v, u);
        } else {
            int ans = walkOnSeg(1, 1, nArr, v, nArr, u);
            cout << ans << '\n';
        }
    }
}

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

    process();
    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	59 ms	7548 KB	Output is correct
5	Correct	64 ms	5684 KB	Output is correct
6	Correct	72 ms	7268 KB	Output is correct
7	Correct	70 ms	7508 KB	Output is correct