src/test/aoj_DSL_2_D.cpp

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

Depends on

• src/dual_segtree.hpp
• src/template.hpp

Code

// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_D
#include "../dual_segtree.hpp"

using F = pair<int, int>;
F id() { return {-1, INT_MAX}; }
void cmpo(const F& f, F& g) {
    if(g.fi < f.fi) g = f;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    dual_segtree<F, id, cmpo> seg(n);
    rep(qi, q) {
        int o;
        cin >> o;
        if(o == 0) {
            int s, t, x;
            cin >> s >> t >> x;
            t++;
            seg.apply(s, t, {qi, x});
        }
        else {
            int i;
            cin >> i;
            cout << seg.get(i).se << "\n";
        }
    }
}

#line 1 "src/test/aoj_DSL_2_D.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_D
#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 3 "src/dual_segtree.hpp"

//伝搬一切しないver
template<class F, F (*id)(), void (*cmpo)(const F&, F&)> struct dual_segtree {
    dual_segtree(): dual_segtree(1) {}
    explicit dual_segtree(int n_): n(__bit_ceil(n_)), d(2 * n, id()) {}
    void apply(int l, int r, F f) {
        if(l == r) return;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) cmpo(f, d[l++]);
            if(r & 1) cmpo(f, d[--r]);
        }
    }
    F get(int i) {
        F r = id();
        for(i += n; i; i >>= 1) cmpo(d[i], r);
        return r;
    }
private:
    int n;
    vector<F> d;
};
#line 3 "src/test/aoj_DSL_2_D.cpp"

using F = pair<int, int>;
F id() { return {-1, INT_MAX}; }
void cmpo(const F& f, F& g) {
    if(g.fi < f.fi) g = f;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    dual_segtree<F, id, cmpo> seg(n);
    rep(qi, q) {
        int o;
        cin >> o;
        if(o == 0) {
            int s, t, x;
            cin >> s >> t >> x;
            t++;
            seg.apply(s, t, {qi, x});
        }
        else {
            int i;
            cin >> i;
            cout << seg.get(i).se << "\n";
        }
    }
}

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	3 MB
g++	01_rand_03.in	AC	4 ms	4 MB
g++	01_rand_04.in	AC	4 ms	4 MB
g++	01_rand_05.in	AC	6 ms	4 MB
g++	02_corner_00.in	AC	4 ms	4 MB
g++	02_corner_01.in	AC	4 ms	4 MB
g++	03_large_00.in	AC	6 ms	4 MB
g++	03_large_01.in	AC	7 ms	4 MB
g++	03_large_02.in	AC	7 ms	4 MB
g++	03_large_03.in	AC	7 ms	4 MB
g++	04_maximum_00.in	AC	24 ms	5 MB
g++	04_maximum_01.in	AC	26 ms	5 MB
g++	04_maximum_02.in	AC	27 ms	5 MB
g++	04_maximum_03.in	AC	25 ms	5 MB
g++	05_critical_00.in	AC	21 ms	5 MB
g++	05_critical_01.in	AC	19 ms	5 MB
g++	05_critical_02.in	AC	23 ms	6 MB
g++	05_critical_03.in	AC	23 ms	5 MB
clang++	00_sample_00.in	AC	5 ms	4 MB
clang++	00_sample_01.in	AC	4 ms	4 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	4 MB
clang++	01_rand_03.in	AC	4 ms	4 MB
clang++	01_rand_04.in	AC	5 ms	4 MB
clang++	01_rand_05.in	AC	6 ms	4 MB
clang++	02_corner_00.in	AC	4 ms	4 MB
clang++	02_corner_01.in	AC	4 ms	4 MB
clang++	03_large_00.in	AC	7 ms	4 MB
clang++	03_large_01.in	AC	7 ms	4 MB
clang++	03_large_02.in	AC	7 ms	4 MB
clang++	03_large_03.in	AC	7 ms	4 MB
clang++	04_maximum_00.in	AC	24 ms	5 MB
clang++	04_maximum_01.in	AC	25 ms	5 MB
clang++	04_maximum_02.in	AC	27 ms	5 MB
clang++	04_maximum_03.in	AC	25 ms	5 MB
clang++	05_critical_00.in	AC	22 ms	6 MB
clang++	05_critical_01.in	AC	19 ms	5 MB
clang++	05_critical_02.in	AC	23 ms	6 MB
clang++	05_critical_03.in	AC	23 ms	5 MB

Back to top page