src/test/aoj_DSL_2_A.cpp

• View this file on GitHub
• Last update: 2025-10-08 01:18:35+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A

Depends on

• Segment Tree (src/segtree.hpp)
• src/template.hpp

Code

// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A
#include "../segtree.hpp"

int op(int l, int r) { return min(l, r); }
int e() { return INT_MAX; }

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

    int n, q;
    cin >> n >> q;
    segtree<int, op, e> seg(n);
    while(q--) {
        int com, x, y;
        cin >> com >> x >> y;
        if(com == 0) {
            seg.set(x, y);
        }
        else {
            cout << seg.prod(x, y + 1) << "\n";
        }
    }
}

#line 1 "src/test/aoj_DSL_2_A.cpp"
// competitive-verifier: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A
#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/segtree.hpp"

template<class S, S (*op)(S, S), S (*e)()> struct segtree {
    int n;
    vector<S> d;
    segtree(): segtree(1) {}
    explicit segtree(int n_): segtree(vector<S>(n_, e())) {}
    explicit segtree(const vector<S>& a): n(__bit_ceil(si(a))), d(n * 2, e()) {
        rep(i, si(a)) d[n + i] = a[i];
        for(int i = n; --i;) d[i] = op(d[i * 2], d[i * 2 + 1]);
    }
    void set(int i, S x) {
        for(d[i += n] = x; i >>= 1;) d[i] = op(d[i * 2], d[i * 2 + 1]);
    }
    S get(int i) { return d[i + n]; }
    S prod(int l, int r) {
        S L = e(), R = e();
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) L = op(L, d[l++]);
            if(r & 1) R = op(d[--r], R);
        }
        return op(L, R);
    }
    template<typename F> int max_right(int l, F f) const {
        if(l == n) return n;
        l += n;
        S sm = e();
        do {
            while(~l & 1) l >>= 1;
            if(!f(op(sm, d[l]))) {
                while(l < n) {
                    l <<= 1;
                    if(f(op(sm, d[l]))) sm = op(sm, d[l++]);
                }
                return l - n;
            }
            sm = op(sm, d[l++]);
        } while((l & -l) != l);
        return n;
    }
    template<typename F> int min_left(int r, F f) const {
        if(!r) return 0;
        r += n;
        S sm = e();
        do {
            r--;
            while(r > 1 and r & 1) r >>= 1;
            if(!f(op(d[r], sm))) {
                while(r < n) {
                    r = (2 * r + 1);
                    if(f(op(d[r], sm))) sm = op(d[r--], sm);
                }
                return r + 1 - n;
            }
            sm = op(d[r], sm);
        } while((r & -r) != r);
        return 0;
    }
};

template<class T> using SegtreeFrom = segtree<typename T::S, T::op, T::e>;
#line 3 "src/test/aoj_DSL_2_A.cpp"

int op(int l, int r) { return min(l, r); }
int e() { return INT_MAX; }

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

    int n, q;
    cin >> n >> q;
    segtree<int, op, e> seg(n);
    while(q--) {
        int com, x, y;
        cin >> com >> x >> y;
        if(com == 0) {
            seg.set(x, y);
        }
        else {
            cout << seg.prod(x, y + 1) << "\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_small_00.in	AC	6 ms	4 MB
g++	00_small_01.in	AC	4 ms	4 MB
g++	00_small_02.in	AC	4 ms	4 MB
g++	00_small_03.in	AC	4 ms	4 MB
g++	01_rand_00.in	AC	4 ms	4 MB
g++	01_rand_01.in	AC	5 ms	4 MB
g++	01_rand_02.in	AC	4 ms	4 MB
g++	01_rand_03.in	AC	4 ms	4 MB
g++	02_biased_00.in	AC	4 ms	4 MB
g++	02_biased_01.in	AC	4 ms	4 MB
g++	02_biased_02.in	AC	4 ms	4 MB
g++	02_biased_03.in	AC	23 ms	4 MB
g++	03_rand_00.in	AC	5 ms	4 MB
g++	03_rand_01.in	AC	6 ms	4 MB
g++	03_rand_02.in	AC	6 ms	4 MB
g++	03_rand_03.in	AC	7 ms	4 MB
g++	03_rand_04.in	AC	30 ms	5 MB
g++	03_rand_05.in	AC	30 ms	5 MB
g++	04_maximum_00.in	AC	30 ms	5 MB
g++	04_maximum_01.in	AC	31 ms	5 MB
clang++	00_small_00.in	AC	5 ms	4 MB
clang++	00_small_01.in	AC	4 ms	4 MB
clang++	00_small_02.in	AC	4 ms	4 MB
clang++	00_small_03.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++	02_biased_00.in	AC	4 ms	4 MB
clang++	02_biased_01.in	AC	4 ms	4 MB
clang++	02_biased_02.in	AC	4 ms	4 MB
clang++	02_biased_03.in	AC	23 ms	4 MB
clang++	03_rand_00.in	AC	5 ms	4 MB
clang++	03_rand_01.in	AC	6 ms	4 MB
clang++	03_rand_02.in	AC	6 ms	4 MB
clang++	03_rand_03.in	AC	7 ms	4 MB
clang++	03_rand_04.in	AC	30 ms	5 MB
clang++	03_rand_05.in	AC	31 ms	5 MB
clang++	04_maximum_00.in	AC	30 ms	5 MB
clang++	04_maximum_01.in	AC	30 ms	5 MB

Back to top page