Test/AtCoder/abc196_e.test.cpp

• View this file on GitHub
• Last update: 2025-06-27 19:09:40+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc196/submissions/67097963
• Link: https://atcoder.jp/contests/abc196/tasks/abc196_e

Depends on

• Src/Algebra/Monoid/ClampAddMonoid.hpp

Code

// #define PROBLEM "https://atcoder.jp/contests/abc196/tasks/abc196_e"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AtCoder Beginner Contest 196 E - Filters
 * https://atcoder.jp/contests/abc196/submissions/67097963
 */

#include "../../Src/Algebra/Monoid/ClampAddMonoid.hpp"
using namespace zawa;

#include <cassert>
#include <iostream>

int main() {
#ifdef ATCODER
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int N;
    std::cin >> N;
    using M = ClampAddMonoid<long long, (long long)1e18>;
    using D = typename M::Element;
    D f = M::identity();
    while (N--) {
        int a, t;
        std::cin >> a >> t;
        if (t == 1) f = M::operation(f, D::add(a));
        else if (t == 2) f = M::operation(f, D::chmax(a));
        else if (t == 3) f = M::operation(f, D::chmin(a));
        else assert(false);
    }
    int Q;
    std::cin >> Q;
    while (Q--) {
        int x;
        std::cin >> x;
        std::cout << f(x) << '\n';
    }
#else
    std::cout << "Hello World\n";
#endif
}

#line 1 "Test/AtCoder/abc196_e.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/abc196/tasks/abc196_e"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * AtCoder Beginner Contest 196 E - Filters
 * https://atcoder.jp/contests/abc196/submissions/67097963
 */

#line 2 "Src/Algebra/Monoid/ClampAddMonoid.hpp"

#include <algorithm>
#include <concepts>
#include <utility>
#include <optional>

namespace zawa {

template <std::totally_ordered T, T INF>
struct ClampAdd {

    static_assert(INF >= T{0}, "ClampAdd<T, INF>'s INF must be non negative");

    T low = -INF, high = INF, plus = 0;

    ClampAdd() = default; 

    ClampAdd(T l, T h, T p) : low{l}, high{h}, plus{p} {}

    static ClampAdd<T, INF> chmin(T x) {
        return {-INF, x, T{0}};
    }

    static ClampAdd<T, INF> chmax(T x) {
        return {x, INF, T{0}};
    }

    static ClampAdd<T, INF> add(T x) {
        return {-INF, INF, x};
    }

    T operator()(T x) const {
        return std::clamp(x, low, high) + plus;
    }
};

// ref: https://rsm9.hatenablog.com/entry/2021/02/01/220408
template <std::totally_ordered T, T INF>
struct ClampAddMonoid {

    using Element = ClampAdd<T, INF>;

    static Element identity() {
        return Element{};
    }

    static Element operation(const Element& L, const Element& R) {
        T low   = std::max(std::min(L.low + L.plus, R.high),  R.low) - L.plus;
        T high  = std::min(std::max(L.high + L.plus, R.low), R.high) - L.plus;
        T plus  = L.plus + R.plus;
        return Element{low, high, plus};
    }

};

} // namespace zawa
#line 10 "Test/AtCoder/abc196_e.test.cpp"
using namespace zawa;

#include <cassert>
#include <iostream>

int main() {
#ifdef ATCODER
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int N;
    std::cin >> N;
    using M = ClampAddMonoid<long long, (long long)1e18>;
    using D = typename M::Element;
    D f = M::identity();
    while (N--) {
        int a, t;
        std::cin >> a >> t;
        if (t == 1) f = M::operation(f, D::add(a));
        else if (t == 2) f = M::operation(f, D::chmax(a));
        else if (t == 3) f = M::operation(f, D::chmin(a));
        else assert(false);
    }
    int Q;
    std::cin >> Q;
    while (Q--) {
        int x;
        std::cin >> x;
        std::cout << f(x) << '\n';
    }
#else
    std::cout << "Hello World\n";
#endif
}

Back to top page