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
/**
 *          ┏┓    ┏┓
 *          ┏┛┗━━━━━━━┛┗━━━┓
 *          ┃       ┃  
 *          ┃   ━    ┃
 *          ┃ >   < ┃
 *          ┃       ┃
 *          ┃... ⌒ ...  ┃
 *          ┃              ┃
 *          ┗━┓          ┏━┛
 *          ┃          ┃ 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 |     }
      |     ^
# 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