test/psum2d.test.cpp

• View this file on GitHub
• Last update: 2024-03-03 06:51:22+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/DSL_5_B

Depends on

• 二次元累積和 (C++/math/psum/psum2d.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_5_B"
#include <iostream>
#include <algorithm>
#include "C++/math/psum/psum2d.hpp"
constexpr int m = 1000;
int main() {
    std::cin.tie(nullptr) -> sync_with_stdio(false);
    int n;
    std::cin >> n;
    psum2d<int64_t> p(m, m);
    while(n--) {
        int x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        p.add(x1, y1, x2, y2, 1);
    }
    p.build();
    int64_t ans = 0;
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < m; ++j) {
            ans = std::max(ans, p.get(i, j));
        }
    }
    std::cout << ans << '\n';
}

#line 1 "test/psum2d.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/DSL_5_B"
#include <iostream>
#include <algorithm>
#line 2 "C++/math/psum/psum2d.hpp"

#include <vector>
template <class T> struct psum2d {
private:
    int h, w;
    std::vector<std::vector<T>> data;
public:
    psum2d(const int h, const int w): h(h + 3), w(w + 3), data(h + 3, std::vector<T>(w + 3)){}
    psum2d(const std::vector<std::vector<T>> &v): h(v.size() + 3), w(v[0].size() + 3), data(v.size() + 3, std::vector<T>(v[0].size() + 3)) {
        for(size_t i = 0; i < v.size(); ++i) {
            for(size_t j = 0; j < v[i].size(); ++j) {
                add(i, j, v[i][j]);
            }
        }
    }
    void add(int i, int j, const T &x) {
		i++;
		j++;
		if(i >= h || j >= w) {
			return;
		}
		data[i][j] += x;
	}
    void add(const int i1, const int j1, const int i2, const int j2, const T &x) {
		add(i1, j1, x);
		add(i1, j2, -x);
		add(i2, j1, -x);
		add(i2, j2, x);
	}
    void build() {
		for(int i = 0; ++i < h;) {
			for(int j = 0; ++j < w;) {
				data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
			}
		}
	}
    T get(const int i1, const int j1, const int i2, const int j2) const { return data[i2][j2] - data[i1][j2] - data[i2][j1] + data[i1][j1]; }
    T get(const int i, const int j) const { return data[i + 1][j + 1]; }
};

/**
 * @brief 二次元累積和
 */
#line 5 "test/psum2d.test.cpp"
constexpr int m = 1000;
int main() {
    std::cin.tie(nullptr) -> sync_with_stdio(false);
    int n;
    std::cin >> n;
    psum2d<int64_t> p(m, m);
    while(n--) {
        int x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        p.add(x1, y1, x2, y2, 1);
    }
    p.build();
    int64_t ans = 0;
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < m; ++j) {
            ans = std::max(ans, p.get(i, j));
        }
    }
    std::cout << ans << '\n';
}

Back to top page