test/DualSegtree.test.cpp

• View this file on GitHub
• Last update: 2025-07-04 15:57:54+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_D

Depends on

• DualSegtree.cpp

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	AC	5 ms	4 MB
g++	00_sample_01.in	AC	4 ms	4 MB
g++	01_rand_00.in	AC	4 ms	4 MB
g++	01_rand_01.in	AC	4 ms	4 MB
g++	01_rand_02.in	AC	4 ms	4 MB
g++	01_rand_03.in	AC	5 ms	3 MB
g++	01_rand_04.in	AC	6 ms	3 MB
g++	01_rand_05.in	AC	13 ms	4 MB
g++	02_corner_00.in	AC	5 ms	3 MB
g++	02_corner_01.in	AC	4 ms	4 MB
g++	03_large_00.in	AC	14 ms	4 MB
g++	03_large_01.in	AC	16 ms	4 MB
g++	03_large_02.in	AC	15 ms	4 MB
g++	03_large_03.in	AC	16 ms	4 MB
g++	04_maximum_00.in	AC	108 ms	5 MB
g++	04_maximum_01.in	AC	121 ms	5 MB
g++	04_maximum_02.in	AC	107 ms	5 MB
g++	04_maximum_03.in	AC	128 ms	5 MB
g++	05_critical_00.in	AC	102 ms	5 MB
g++	05_critical_01.in	AC	119 ms	5 MB
g++	05_critical_02.in	AC	68 ms	5 MB
g++	05_critical_03.in	AC	70 ms	5 MB
clang++	00_sample_00.in	AC	5 ms	3 MB
clang++	00_sample_01.in	AC	4 ms	3 MB
clang++	01_rand_00.in	AC	4 ms	4 MB
clang++	01_rand_01.in	AC	4 ms	4 MB
clang++	01_rand_02.in	AC	4 ms	3 MB
clang++	01_rand_03.in	AC	5 ms	4 MB
clang++	01_rand_04.in	AC	8 ms	4 MB
clang++	01_rand_05.in	AC	20 ms	3 MB
clang++	02_corner_00.in	AC	4 ms	4 MB
clang++	02_corner_01.in	AC	4 ms	3 MB
clang++	03_large_00.in	AC	19 ms	4 MB
clang++	03_large_01.in	AC	16 ms	4 MB
clang++	03_large_02.in	AC	15 ms	4 MB
clang++	03_large_03.in	AC	17 ms	4 MB
clang++	04_maximum_00.in	AC	117 ms	5 MB
clang++	04_maximum_01.in	AC	105 ms	5 MB
clang++	04_maximum_02.in	AC	148 ms	5 MB
clang++	04_maximum_03.in	AC	119 ms	5 MB
clang++	05_critical_00.in	AC	108 ms	5 MB
clang++	05_critical_01.in	AC	122 ms	5 MB
clang++	05_critical_02.in	AC	68 ms	5 MB
clang++	05_critical_03.in	AC	70 ms	5 MB

Back to top page