Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anmichi/Library

:heavy_check_mark: test/DualSegtree.test.cpp

Depends on

Code

// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_D
#include "../DualSegtree.cpp"
int op(int a, int b) { return (b == -1 ? a : b); }
int e() { return -1; }
int main() {
    int n, q;
    cin >> n >> q;
    dual_segtree<int, op, e> seg(vector<int>(n, INT_MAX));
    while (q--) {
        int type;
        cin >> type;
        if (type == 0) {
            int s, t, x;
            cin >> s >> t >> x;
            seg.apply(s, t + 1, x);
        } else {
            int k;
            cin >> k;
            cout << seg.get(k) << endl;
        }
    }
}
#line 1 "test/DualSegtree.test.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_D
#line 1 "DualSegtree.cpp"
#include <bits/stdc++.h>
using namespace std;
template <class S, S (*op)(S, S), S (*e)()>
struct dual_segtree {
    int sz = 1, log = 0;
    vector<S> lz;
    dual_segtree() = default;
    dual_segtree(int n) : dual_segtree(vector<S>(n, e())) {}
    dual_segtree(vector<S> a) {
        int n = a.size();
        while (sz < n) {
            sz <<= 1;
            log++;
        }
        lz.assign(sz << 1, e());
        for (int i = 0; i < n; i++) lz[i + sz] = a[i];
    }
    void push(int k) {
        int b = __builtin_ctz(k);
        for (int d = log; d > b; d--) {
            lz[k >> d << 1] = op(lz[k >> d << 1], lz[k >> d]);
            lz[k >> d << 1 | 1] = op(lz[k >> d << 1 | 1], lz[k >> d]);
            lz[k >> d] = e();
        }
    }
    void apply(int l, int r, S x) {
        l += sz, r += sz;
        push(l);
        push(r);
        while (l < r) {
            if (l & 1) {
                lz[l] = op(lz[l], x);
                l++;
            }
            if (r & 1) {
                r--;
                lz[r] = op(lz[r], x);
            }
            l >>= 1, r >>= 1;
        }
    }
    S get(int k) {
        k += sz;
        S res = e();
        while (k) {
            res = op(res, lz[k]);
            k >>= 1;
        }
        return res;
    }
};
#line 3 "test/DualSegtree.test.cpp"
int op(int a, int b) { return (b == -1 ? a : b); }
int e() { return -1; }
int main() {
    int n, q;
    cin >> n >> q;
    dual_segtree<int, op, e> seg(vector<int>(n, INT_MAX));
    while (q--) {
        int type;
        cin >> type;
        if (type == 0) {
            int s, t, x;
            cin >> s >> t >> x;
            seg.apply(s, t + 1, x);
        } else {
            int k;
            cin >> k;
            cout << seg.get(k) << endl;
        }
    }
}

Test cases

Env Name Status Elapsed Memory
g++ 00_sample_00.in :heavy_check_mark: AC 5 ms 4 MB
g++ 00_sample_01.in :heavy_check_mark: AC 4 ms 4 MB
g++ 01_rand_00.in :heavy_check_mark: AC 4 ms 4 MB
g++ 01_rand_01.in :heavy_check_mark: AC 4 ms 4 MB
g++ 01_rand_02.in :heavy_check_mark: AC 4 ms 4 MB
g++ 01_rand_03.in :heavy_check_mark: AC 5 ms 3 MB
g++ 01_rand_04.in :heavy_check_mark: AC 6 ms 3 MB
g++ 01_rand_05.in :heavy_check_mark: AC 13 ms 4 MB
g++ 02_corner_00.in :heavy_check_mark: AC 5 ms 3 MB
g++ 02_corner_01.in :heavy_check_mark: AC 4 ms 4 MB
g++ 03_large_00.in :heavy_check_mark: AC 14 ms 4 MB
g++ 03_large_01.in :heavy_check_mark: AC 16 ms 4 MB
g++ 03_large_02.in :heavy_check_mark: AC 15 ms 4 MB
g++ 03_large_03.in :heavy_check_mark: AC 16 ms 4 MB
g++ 04_maximum_00.in :heavy_check_mark: AC 108 ms 5 MB
g++ 04_maximum_01.in :heavy_check_mark: AC 121 ms 5 MB
g++ 04_maximum_02.in :heavy_check_mark: AC 107 ms 5 MB
g++ 04_maximum_03.in :heavy_check_mark: AC 128 ms 5 MB
g++ 05_critical_00.in :heavy_check_mark: AC 102 ms 5 MB
g++ 05_critical_01.in :heavy_check_mark: AC 119 ms 5 MB
g++ 05_critical_02.in :heavy_check_mark: AC 68 ms 5 MB
g++ 05_critical_03.in :heavy_check_mark: AC 70 ms 5 MB
clang++ 00_sample_00.in :heavy_check_mark: AC 5 ms 3 MB
clang++ 00_sample_01.in :heavy_check_mark: AC 4 ms 3 MB
clang++ 01_rand_00.in :heavy_check_mark: AC 4 ms 4 MB
clang++ 01_rand_01.in :heavy_check_mark: AC 4 ms 4 MB
clang++ 01_rand_02.in :heavy_check_mark: AC 4 ms 3 MB
clang++ 01_rand_03.in :heavy_check_mark: AC 5 ms 4 MB
clang++ 01_rand_04.in :heavy_check_mark: AC 8 ms 4 MB
clang++ 01_rand_05.in :heavy_check_mark: AC 20 ms 3 MB
clang++ 02_corner_00.in :heavy_check_mark: AC 4 ms 4 MB
clang++ 02_corner_01.in :heavy_check_mark: AC 4 ms 3 MB
clang++ 03_large_00.in :heavy_check_mark: AC 19 ms 4 MB
clang++ 03_large_01.in :heavy_check_mark: AC 16 ms 4 MB
clang++ 03_large_02.in :heavy_check_mark: AC 15 ms 4 MB
clang++ 03_large_03.in :heavy_check_mark: AC 17 ms 4 MB
clang++ 04_maximum_00.in :heavy_check_mark: AC 117 ms 5 MB
clang++ 04_maximum_01.in :heavy_check_mark: AC 105 ms 5 MB
clang++ 04_maximum_02.in :heavy_check_mark: AC 148 ms 5 MB
clang++ 04_maximum_03.in :heavy_check_mark: AC 119 ms 5 MB
clang++ 05_critical_00.in :heavy_check_mark: AC 108 ms 5 MB
clang++ 05_critical_01.in :heavy_check_mark: AC 122 ms 5 MB
clang++ 05_critical_02.in :heavy_check_mark: AC 68 ms 5 MB
clang++ 05_critical_03.in :heavy_check_mark: AC 70 ms 5 MB
Back to top page