verify/Datastructure_1dimos.test.cpp

View this file on GitHub
Last update: 2025-01-10 00:00:54+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0360?year=2017

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0360?year=2017"

#include "../Utility/template.hpp"
#include "../Datastructure/imos1d.hpp"


int main() {
    imos1d<ll> imos(1001);
    int a, b;
    cin >> a >> b;
    imos.imos_add(a, b, 1);

    int n;
    cin >> n;
    while(n--) {
        int s, f;
        cin >> s >> f;
        imos.imos_add(s, f, 1);
    }

    imos.build();

    rep(i, 0, 1001) {
        if(imos[i] > 1) {
            cout << 1 << endl;
            exit(0);
        }
    }
    cout << 0 << endl;
    exit(0);
}

#line 1 "verify/Datastructure_1dimos.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0360?year=2017"

#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/imos1d.hpp"
TT struct imos1d {
    int n;
    vec<T> dat;
    bool built = false;

    imos1d(int n = 0) : n(n) { dat.resize(n, T()); }

    void imos_add(int i, T x) {
        assert(built == false);
        assert(0 <= i && i < n);
        dat[i] += x;
        if(i + 1 < n) dat[i + 1] -= x;
    }

    void imos_add(int l, int r, T x) {
        assert(0 <= l && r <= n && l <= r);
        dat[l] += x;
        if (r < n) dat[r] -= x;
    }

    void build() {
        rep(i, 0, n - 1) dat[i + 1] += dat[i];
        built = true;
    }

    T operator[](int i) const {
        assert(built == true);
        assert(0 <= i && i < n);
        return dat[i];
    }
};

/*
@brief 1次元imos法
*/
#line 5 "verify/Datastructure_1dimos.test.cpp"


int main() {
    imos1d<ll> imos(1001);
    int a, b;
    cin >> a >> b;
    imos.imos_add(a, b, 1);

    int n;
    cin >> n;
    while(n--) {
        int s, f;
        cin >> s >> f;
        imos.imos_add(s, f, 1);
    }

    imos.build();

    rep(i, 0, 1001) {
        if(imos[i] > 1) {
            cout << 1 << endl;
            exit(0);
        }
    }
    cout << 0 << endl;
    exit(0);
}