test/accum2d.test.cpp

View this file on GitHub
Last update: 2023-01-20 10:35:01+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/5/DSL_5_B

Depends on

accum2d (二次元累積和) (src/dataStructure/accum2d.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/5/DSL_5_B"

#include "../src/dataStructure/accum2d.hpp"

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
	int N; std::cin >> N;
	std::vector A(1001, std::vector(1001, 0));
	for (int _ = 0 ; _ < N ; _++) {
		int x1, y1, x2, y2; std::cin >> x1 >> y1 >> x2 >> y2;
		A[y1][x1]++;
		A[y1][x2]--;
		A[y2][x1]--;
		A[y2][x2]++;
	}
	zawa::accum2d S(A);
	int ans = 0;
	for (const auto& s : S) {
		ans = std::max(ans, *max_element(s.begin(), s.end()));
	}
	std::cout << ans << std::endl;
}

#line 1 "test/accum2d.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/5/DSL_5_B"

#line 2 "src/dataStructure/accum2d.hpp"

#include <vector>
#include <utility>

namespace zawa {

template <class T>
struct accum2d : std::vector<std::vector<T>> {
	accum2d() {
		(*this).push_back({ T() });
	}
	accum2d(const std::vector<std::vector<T>>& A) : std::vector<std::vector<T>>(A.size() + 1, std::vector<T>(A[0].size() + 1, T())) {
		for (std::size_t i = 0 ; i < A.size() ; i++) {
			for (std::size_t j = 0 ; j < A[i].size() ; j++) {
				(*this)[i + 1][j + 1] = (*this)[i][j + 1] + (*this)[i + 1][j] - (*this)[i][j] + A[i][j];
			}
		}
	}
	T sum(std::size_t y1, std::size_t x1, std::size_t y2, std::size_t x2) {
		return (*this)[y2][x2] - (*this)[y1][x2] - (*this)[y2][x1] + (*this)[y1][x1];
	}
	T sum(std::pair<std::size_t, std::size_t> p1, std::pair<std::size_t, std::size_t> p2) {
		return sum(p1.first, p1.second, p2.first, p2.second);
	}
};

} // namespace zawa
#line 4 "test/accum2d.test.cpp"

#include <iostream>
#line 7 "test/accum2d.test.cpp"
#include <algorithm>

int main() {
	int N; std::cin >> N;
	std::vector A(1001, std::vector(1001, 0));
	for (int _ = 0 ; _ < N ; _++) {
		int x1, y1, x2, y2; std::cin >> x1 >> y1 >> x2 >> y2;
		A[y1][x1]++;
		A[y1][x2]--;
		A[y2][x1]--;
		A[y2][x2]++;
	}
	zawa::accum2d S(A);
	int ans = 0;
	for (const auto& s : S) {
		ans = std::max(ans, *max_element(s.begin(), s.end()));
	}
	std::cout << ans << std::endl;
}