test/Imos.test.cpp

• View this file on GitHub
• Last update: 2021-03-05 15:06:25+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2013

Depends on

• DataStructure/Imos.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2013"
#include "./../DataStructure/Imos.cpp"
#include <iostream>
#include <algorithm>
using namespace std;

int input_time() {
	int h, m, s;
	char c;
	cin >> h >> c >> m >> c >> s;
	return h * 3600 + m * 60 + s;
}

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

	while (true) {
		int n;
		cin >> n;
		if (n == 0) break;
		Imos<int> imos(24 * 60 * 60);
		for (int i = 0; i < n; ++i) {
			int s = input_time(), t = input_time();
			imos.add(s, t);
		}
		imos.build();
		auto a = imos.to_a();
		cout << *max_element(a.begin(), a.end()) << '\n';
	}
}

#line 1 "test/Imos.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2013"
#line 2 "DataStructure/Imos.cpp"
#include <vector>
#include <utility>
#include <algorithm>
#include <cassert>

template <class T> class Imos {
public:
	using value_type = T;

private:
	int n;
	std::vector<value_type> table;
	bool builded = false;

public:
	Imos() = default;
	Imos(int _n) : n(_n), table(_n + 1) {}
	void add(int l, int r, value_type v = 1) {
		assert(!builded);
		l = std::clamp(l, 0, n);
		r = std::clamp(r, 0, n);
		if (l < r) {
			table[l] += v;
			table[r] -= v;
		}
	}
	void add(const std::pair<int, int>& section, value_type v = 1) {
		add(section.first, section.second, v);
	}
	void add_closed(int l, int r, value_type v = 1) {
		add(l, r + 1, v);
	}
	void add_closed(const std::pair<int, int>& section, value_type v = 1) {
		add_closed(section.first, section.second, v);
	}
	void build() {
		builded = true;
		for (int i = 1; i < n; ++i) {
			table[i] += table[i - 1];
		}
	}
	value_type operator[](int i) const {
		assert(builded);
		return table[i];
	}
	const std::vector<value_type>& operator*() const {
		assert(builded);
		return table;
	}
	std::vector<value_type> to_a() const {
		return std::vector(table.begin(), table.begin() + n);
	}
};
#line 3 "test/Imos.test.cpp"
#include <iostream>
#line 5 "test/Imos.test.cpp"
using namespace std;

int input_time() {
	int h, m, s;
	char c;
	cin >> h >> c >> m >> c >> s;
	return h * 3600 + m * 60 + s;
}

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

	while (true) {
		int n;
		cin >> n;
		if (n == 0) break;
		Imos<int> imos(24 * 60 * 60);
		for (int i = 0; i < n; ++i) {
			int s = input_time(), t = input_time();
			imos.add(s, t);
		}
		imos.build();
		auto a = imos.to_a();
		cout << *max_element(a.begin(), a.end()) << '\n';
	}
}

Back to top page