Submission #961336

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
961336	2024-04-11T20:49:41 Z	vjudge1	Deda (COCI17_deda)	C++17	80 / 140	1000 ms	12780 KB

deda

/**
 *　　　　　　  　　┏┓　　 　┏┓
 * 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　  　　┃　　　　　　　┃ 　
 * 　　　　　  　　┃　　　━　　 　┃
 * 　　　　　  　　┃　＞　　　＜　┃
 * 　　　　　  　　┃　　　　　　　┃
 * 　　　　　  　　┃...　⌒　... 　┃
 * 　　　　　　  　┃              ┃
 * 　　　　　　  　┗━┓          ┏━┛
 * 　　　　　　　　　┃          ┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃          ┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┃  　　　　　　
 * 　　　　　　　　　┃          ┃
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┗━━━┓
 * 　　　　　　　　　┃              ┣┓
 * 　　　　　　　　　┃              ┏┛
 * 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛
 * 　　　　　　　　　　┃┫┫       ┃┫┫
 * 　　　　　　　　　　┗┻┛       ┗┻┛
 */
#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;
int ans = 1e18;
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;
    }
    node xxxquery(int id, int l, int r, int sl, int sr, int tag) {
        if (sl <= l && r <= sr) {  // 目前這個區間在查詢區間內
            if (seg[id].val > tag) return seg[id];
            if (l == r) {
                ans = min(ans, l);
                return seg[id];
            }
        }
        int mid = (l + r) >> 1;
        node ans1, ans2;
        bool f1 = 0, f2 = 0;
        if (sl <= mid) {  // 左區間跟查詢區間有交集
            ans1 = xxxquery(cl(id), l, mid, sl, sr, tag);
            f1 = 1;
        }
        if (mid < sr) {  // 右區間跟查詢區間有交集
            ans2 = xxxquery(cr(id), mid + 1, r, sl, sr, tag);
            f2 = 1;
        }
        if (f1 && f2) {
            return {min(ans1.val, ans2.val)};
        }
        if (f1) return ans1;
        if (f2) return ans2;
    }
} 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;
            ans = 1e18;
            tree.xxxquery(1, 1, n, b, n, y);
            if (ans == 1e18) ans = -1;
            cout << ans << '\n';
        }
    }
}

Compilation message

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

Subtask #1

80.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	600 KB	Output is correct
3	Correct	5 ms	564 KB	Output is correct
4	Correct	351 ms	12780 KB	Output is correct
5	Execution timed out	1071 ms	5364 KB	Time limit exceeded
6	Execution timed out	1062 ms	7372 KB	Time limit exceeded
7	Execution timed out	1056 ms	9344 KB	Time limit exceeded