Submission #954303

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
954303	2024-03-27T15:31:53 Z	vjudge1	Deda (COCI17_deda)	C++17	140 / 140	450 ms	12756 KB

deda

#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int long long

#define cl(x) (x << 1)
#define cr(x) (x << 1) + 1

const int INF = 1e17;

struct node {
    int val;
};
struct SEG {
    int n;
    vector<node> seg;
    vector<node> arr;
    void init(int a) {
        n = a;
        seg.resize(4 * n + 5);
        arr.resize(a + 1);
    }
    void pull(int id) {
        auto a = seg[cl(id)];
        auto b = seg[cr(id)];
        seg[id] = {min(a.val, b.val)};
    }
    void build(int id, int l, int r) {
        if (l == r) {
            seg[id] = arr[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(cl(id), l, mid);
        build(cr(id), mid + 1, r);
        pull(id);
    }
    void update(int id, int l, int r, int x, int v) {
        if (l == r) {
            seg[id] = {v};
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) {
            update(cl(id), l, mid, x, v);
        }
        if (mid < x) {
            update(cr(id), mid + 1, r, x, v);
        }
        pull(id);
    }
    node query(int id, int l, int r, int sl, int sr) {
        if (sl <= l && r <= sr) {  // 目前這個區間在查詢區間內
            return seg[id];
        }
        int mid = (l + r) >> 1;
        node ans1, ans2;
        bool f1 = 0, f2 = 0;
        if (sl <= mid) {  // 左區間跟查詢區間有交集
            ans1 = query(cl(id), l, mid, sl, sr);
            f1 = 1;
        }
        if (mid < sr) {  // 右區間跟查詢區間有交集
            ans2 = query(cr(id), mid + 1, r, sl, sr);
            f2 = 1;
        }
        if (f1 && f2) {
            return {min(ans1.val, ans2.val)};
        }
        if (f1) return ans1;
        if (f2) return ans2;
    }
    int fquery(int l, int r, int v) {
        int p = query(1, 1, n, l, r).val;
        if (p > v) return -1;

        while (l != r) {
            int mid = (l + r) >> 1;
            int x = query(1, 1, n, l, mid).val;
            if (x <= v)
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
} tree;

signed main() {
    FASTIO;
    int n, q;
    cin >> n >> q;
    tree.init(n);
    for (int i = 1; i <= n; i++)
        tree.arr[i] = {INF};
    tree.build(1, 1, n);

    for (int i = 0; i < q; i++) {
        char sta;
        int x, a, y, b;
        cin >> sta;
        if (sta == 'M') {
            cin >> x >> a;
            tree.update(1, 1, n, a, x);
        }
        if (sta == 'D') {
            cin >> y >> b;
            cout << tree.fquery(b, n, y) << '\n';
        }
    }
}

Compilation message

deda.cpp: In member function 'node SEG::query(long long int, long long int, long long int, long long int, long long int)':
deda.cpp:72:5: warning: control reaches end of non-void function [-Wreturn-type]
   72 |     }
      |     ^

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	456 KB	Output is correct
3	Correct	5 ms	348 KB	Output is correct
4	Correct	450 ms	12756 KB	Output is correct
5	Correct	360 ms	8252 KB	Output is correct
6	Correct	414 ms	10732 KB	Output is correct
7	Correct	441 ms	12612 KB	Output is correct