Submission #774124

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
774124	2023-07-05T12:11:56 Z	VMaksimoski008	Deda (COCI17_deda)	C++17	140 / 140	677 ms	10972 KB

deda

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define pii pair<int, int>
#define pll pair<long long, long long>
#define debug(x) cout << #x << " = " << x << endl
#define pb push_back
#define eb emplace_back
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int mod = 1e9 + 7;
using namespace std;

void setIO() {
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
}

struct SegTree {
    int n;
    vector<ll> tree;

    SegTree(int n) {
        this->n = n;
        tree.resize(4*n + 5, 0);
        build(1, 0, n-1);
    }

    void build(int u, int l, int r) {
        if(l == r) {
            tree[u] = 1e10;
        } else {
            int m = (l + r) / 2;
            build(2*u, l, m);
            build(2*u+1, m+1, r);
            tree[u] = min(tree[2*u], tree[2*u+1]);
        }
    }

    void update(int u, int tl, int tr, int pos, int val) {
        if(tl == tr) {
            tree[u] = val;
        } else {
            int tm = (tl + tr) / 2;
            if(pos <= tm)
                update(2*u, tl, tm, pos, val);
            else
                update(2*u+1, tm+1, tr, pos, val);
            tree[u] = min(tree[2*u], tree[2*u+1]);
        }
    }

    ll query(int u, int tl, int tr, int l, int r) {
        if(l > r) return 1e10;
        if(l == tl && tr == r) return tree[u];
        int tm = (tl + tr) / 2;
        return min(
            query(2*u, tl, tm, l, min(tm, r)),
            query(2*u+1, tm+1, tr, max(tm+1, l), r)
        );
    }

    void update(int pos, int val) {
        update(1, 0, n-1, pos, val);
    }

    ll query(int l, int r) {
        return query(1, 0, n-1, l, r);
    }

    ll find(int a, int b) {
        ll ans = -1;

        int l=b, r=n-1;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(query(l, mid) <= a) {
                ans = mid;
                r = mid-1;
            } else {
                l = mid + 1;
            }
        }

        return ans;
    }
};

int main() {
    setIO();

    int n, q;
    cin >> n >> q;

    SegTree tree(n+1);
    while(q--) {
        char t;
        int a, b;
        cin >> t >> a >> b;

        if(t == 'D')
            cout << tree.find(a, b) << '\n';
        else
            tree.update(b, a);

    }

    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	6 ms	340 KB	Output is correct
4	Correct	677 ms	10972 KB	Output is correct
5	Correct	424 ms	7396 KB	Output is correct
6	Correct	550 ms	9204 KB	Output is correct
7	Correct	575 ms	10916 KB	Output is correct