test/data-structure/fenwick2d/aoj-dsl-The-Maximum-Number-of-Overlaps.test.cpp

• View this file on GitHub
• Last update: 2023-07-11 10:41:16+08:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B

Depends on

• library/data-structure/fenwick2d.hpp

Code

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

#include <iostream>

#include "../../../library/data-structure/fenwick2d.hpp"

using namespace std;
using namespace felix;

const int N_MAX = 1005;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	fenwick2d<int> fenw(N_MAX, N_MAX);
	for(int i = 0; i < n; i++) {
		int x, y, x2, y2;
		cin >> x >> y >> x2 >> y2;
		fenw.add(x, y, +1);
		fenw.add(x, y2, -1);
		fenw.add(x2, y, -1);
		fenw.add(x2, y2, +1);
	}
	int ans = 0;
	for(int i = 0; i < N_MAX; i++) {
		for(int j = 0; j < N_MAX; j++) {
			ans = max(ans, fenw.get(i + 1, j + 1));
		}
	}
	cout << ans << "\n";
	return 0;
}

#line 1 "test/data-structure/fenwick2d/aoj-dsl-The-Maximum-Number-of-Overlaps.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B"

#include <iostream>

#line 2 "library/data-structure/fenwick2d.hpp"
#include <vector>

#include <cassert>


namespace felix {

template<class S>
struct fenwick2d {
public:
	fenwick2d() : n(0), m(0) {}
	explicit fenwick2d(int _n, int _m) : n(_n), m(_m), data(_n, std::vector<S>(_m)) {}

	void add(int x, int y, S val) {
		assert(0 <= x && 0 <= y);
		if(x >= n || y >= m) {
			return;
		}
		for(int i = x + 1; i <= n; i += i & -i) {
			for(int j = y + 1; j <= m; j += j & -j) {
				data[i - 1][j - 1] += val;
			}
		}
	}

	// [0, x) * [0, y)

	S get(int x, int y) const {
		assert(x <= n && y <= m);
		S ans{};
		for(int i = x; i > 0; i -= i & -i) {
			for(int j = y; j > 0; j -= j & -j) {
				ans += data[i - 1][j - 1];
			}
		}
		return ans;
	}

	// [x, x2) * [y, y2)

	S sum(int x, int y, int x2, int y2) const { return get(x2, y2) - get(x, y2) - get(x2, y) + get(x, y); }

private:
	int n, m;
	std::vector<std::vector<S>> data;
};

} // namespace felix

#line 5 "test/data-structure/fenwick2d/aoj-dsl-The-Maximum-Number-of-Overlaps.test.cpp"
using namespace std;
using namespace felix;

const int N_MAX = 1005;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	fenwick2d<int> fenw(N_MAX, N_MAX);
	for(int i = 0; i < n; i++) {
		int x, y, x2, y2;
		cin >> x >> y >> x2 >> y2;
		fenw.add(x, y, +1);
		fenw.add(x, y2, -1);
		fenw.add(x2, y, -1);
		fenw.add(x2, y2, +1);
	}
	int ans = 0;
	for(int i = 0; i < N_MAX; i++) {
		for(int j = 0; j < N_MAX; j++) {
			ans = max(ans, fenw.get(i + 1, j + 1));
		}
	}
	cout << ans << "\n";
	return 0;
}

Back to top page