verify/aoj_other/aoj_0360.test.cpp

• View this file on GitHub
• Last update: 2023-03-17 17:11:39+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0360

Depends on

• 累積和 (data_structure/cumulative_sum.hpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0360"

#include <bits/stdc++.h>

#include "data_structure/cumulative_sum.hpp"

int main() {
    int a, b, N;
    std::cin >> a >> b >> N;
    CumulativeSum<int> rui(1000);
    for (int i = 0; i < N; i++) {
        int s, f;
        std::cin >> s >> f;
        rui.imos(s, f);
    }
    rui.build();
    bool ok = false;
    for (int i = a; i < b; i++) {
        if (rui.get(i)) ok = true;
    }
    std::cout << ok << '\n';
    return 0;
}

#line 1 "verify/aoj_other/aoj_0360.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0360"

#include <bits/stdc++.h>

#line 2 "data_structure/cumulative_sum.hpp"

template <class T> struct CumulativeSum {
    int n;
    std::vector<T> seg;

    CumulativeSum() = default;

    CumulativeSum(int n) : n(n), seg(n + 1, T(0)) {}

    CumulativeSum(std::vector<T> &a) {
        n = (int)a.size();
        seg.assign(n + 1, T(0));
        for (int i = 0; i < n; i++) seg[i + 1] = seg[i] + a[i];
    }

    // [l, r)
    T sum(int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        return seg[r] - seg[l];
    }

    // A[l] += x, A[l + 1] += x, ... , A[r - 1] += x
    void imos(int l, int r, T x = T(1)) {
        assert(0 <= l and l <= r and r <= n);
        seg[l] += x;
        seg[r] -= x;
    }

    void build() {
        for (int i = 0; i < n; i++) seg[i + 1] += seg[i];
    }

    // return A[p]
    T get(int p) const {
        assert(0 <= p and p < n);
        return seg[p];
    }

    // output
    friend std::ostream &operator<<(std::ostream &os, const CumulativeSum &A) {
        os << "n = " << A.n << "\n";
        for (int i = 0; i <= A.n; i++) os << A.seg[i] << " \n"[i == A.n];
        return os;
    }
};
#line 6 "verify/aoj_other/aoj_0360.test.cpp"

int main() {
    int a, b, N;
    std::cin >> a >> b >> N;
    CumulativeSum<int> rui(1000);
    for (int i = 0; i < N; i++) {
        int s, f;
        std::cin >> s >> f;
        rui.imos(s, f);
    }
    rui.build();
    bool ok = false;
    for (int i = a; i < b; i++) {
        if (rui.get(i)) ok = true;
    }
    std::cout << ok << '\n';
    return 0;
}

Back to top page