test/aoj/dsl/dsl_5_b_cs2d.test.cpp

• View this file on GitHub
• Last update: 2024-11-18 03:25:02+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B

Depends on

• Cumulative Sum 2D (二次元累積和) (lib/data_structure/cumulative_sum_2d.hpp)

Code

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

#include "../../../lib/data_structure/cumulative_sum_2d.hpp"

using namespace std;

int main(){
    int n; cin >> n;
    CumulativeSum2D<long long> s(1002, 1002);
    for(int i = 0; i < n; i++){
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        s.imos(x1, y1, x2, y2, 1);
    }
    s.build();
    long long ans = 0;
    for(int i = 0; i <= 1000; i++){
        for(int j = 0; j <= 1000; j++){
            ans = max(ans, s.sum(0, 0, i, j));
        }
    }
    cout << ans << "\n";
}

#line 1 "test/aoj/dsl/dsl_5_b_cs2d.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B"
#include <iostream>

#line 2 "lib/data_structure/cumulative_sum_2d.hpp"

/**
 * @brief Cumulative Sum 2D (二次元累積和)
 * @docs docs/data_structure/cumulative_sum_2d.md
 */

#include <vector>
#include <cassert>

template <typename T>
struct CumulativeSum2D{
    int H, W;
    std::vector<std::vector<T>> data;

    CumulativeSum2D(const int _H, const int _W) : H(_H), W(_W), data(_H + 3, std::vector<T>(_W + 3, 0)) {}

    void add(int i, int j, const T &z){
        ++i, ++j;
        if(i >= (int) data.size() || j >= (int) data[0].size()) return;
        data[i][j] += z;
    }

    void imos(const int i1, const int j1, const int i2, const int j2, const T &z = 1) {
        assert(0 <= i1 && i1 <= i2 && i2 <= H);
        assert(0 <= j1 && j1 <= j2 && j2 <= W);
        add(i1, j1, z);
        add(i1, j2, -z);
        add(i2, j1, -z);
        add(i2, j2, z);
    }

    void build(){
        for(int i = 1; i < (int) data.size(); ++i){
            for(int j = 1; j < (int) data[i].size(); ++j){
                data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
            }
        }
    }

    inline T imos_get(const int i, const int j) const{
        return data[i + 1][j + 1];
    }

    inline T sum(const int i1, const int j1, const int i2, const int j2) const {
        assert(0 <= i1 && i1 <= i2 && i2 <= H);
        assert(0 <= j1 && j1 <= j2 && j2 <= W);
        return (data[i2][j2] - data[i1][j2] - data[i2][j1] + data[i1][j1]);
    }
};
#line 5 "test/aoj/dsl/dsl_5_b_cs2d.test.cpp"

using namespace std;

int main(){
    int n; cin >> n;
    CumulativeSum2D<long long> s(1002, 1002);
    for(int i = 0; i < n; i++){
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        s.imos(x1, y1, x2, y2, 1);
    }
    s.build();
    long long ans = 0;
    for(int i = 0; i <= 1000; i++){
        for(int j = 0; j <= 1000; j++){
            ans = max(ans, s.sum(0, 0, i, j));
        }
    }
    cout << ans << "\n";
}

Back to top page