Submission #530395

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
530395	2022-02-25T09:37:43 Z	cqtshadow	Deda (COCI17_deda)	C++14	140 / 140	105 ms	7872 KB

deda

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

const int INF = (int)1e9 + 2;

class SegmentTree {
private :
    int n;
    vector<int> val;

    void update(int pos, int l, int r, int id, int nval) {
        if(r < id || id < l) return;
        if(l == r) {
            val[pos] = nval;
            return;
        }
        int mid = (l + r) >> 1;
        update(pos<<1, l, mid, id, nval);
        update(pos<<1|1, mid + 1, r, id, nval);
        val[pos] = min(val[pos<<1], val[pos<<1|1]);
    }

    int findSmallest(int pos, int l, int r, int u, int v, int k) {
        if(v < l || r < u || r < l) return -1;
        if(u <= l && r <= v) {
            if(val[pos] > k) return -1;
            int root = pos;
            int le = l, ri = r;
            while(le < ri) {
                int mid = (le + ri) >> 1;
                if(val[root<<1] <= k) {
                    ri = mid;
                    root = root * 2;
                } else {
                    le = mid + 1;
                    root = root*2 + 1;
                }
            }
            return le;
        }
        int mid = (l + r) >> 1;
        int res = findSmallest(pos<<1, l, mid, u, v, k);
        if(res == -1)
            return findSmallest(pos<<1|1, mid + 1, r, u, v, k);
        return res;
    }

public :
    SegmentTree(int x = 0) {
        this->n = x;
        if(x > 0)
            val.assign(4*x + 1, INF);
    }
    void update(int id, int nval) {
        update(1, 1, n, id, nval);
    }
    int findSmallest(int l, int r, int k) {
        return findSmallest(1, 1, n, l, r, k);
    }
};

SegmentTree myit;
int n, q, x, y;
char c;

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> q;

    myit = SegmentTree(n);

    while(q--) {
        cin >> c >> x >> y;
        if(c == 'M') myit.update(y, x);
        else cout << myit.findSmallest(y, n, x) << '\n';
    }
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	2 ms	328 KB	Output is correct
4	Correct	96 ms	7872 KB	Output is correct
5	Correct	105 ms	5816 KB	Output is correct
6	Correct	90 ms	6944 KB	Output is correct
7	Correct	105 ms	7868 KB	Output is correct