verify/aoj_dsl/aoj_dsl_5_b.test.cpp

• View this file on GitHub
• Last update: 2023-04-16 00:50:22+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B

Depends on

• 2次元累積和 (data_structure/cumulative_sum_2d.hpp)

Code

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

#include <bits/stdc++.h>

#include "data_structure/cumulative_sum_2d.hpp"

int main() {
    int N;
    std::cin >> N;
    int M = 1000;
    CumulativeSum2D<int> rui(M, M);
    while (N--) {
        int x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        rui.imos(x1, y1, x2, y2);
    }
    rui.build();
    int ans = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) {
            ans = std::max(ans, rui.get(i, j));
        }
    }
    std::cout << ans << '\n';
    return 0;
}

#line 1 "verify/aoj_dsl/aoj_dsl_5_b.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B"

#include <bits/stdc++.h>

#line 2 "data_structure/cumulative_sum_2d.hpp"

template <class T> struct CumulativeSum2D {
    int h, w;
    std::vector<std::vector<T>> seg;

    CumulativeSum2D() = default;

    CumulativeSum2D(int h, int w) : h(h), w(w), seg(h + 1, std::vector<T>(w + 1, T(0))) {}

    CumulativeSum2D(std::vector<std::vector<T>> &a) {
        h = (int)a.size();
        assert(h > 0);
        w = (int)a[0].size();
        seg.assign(h + 1, std::vector<T>(w + 1, T(0)));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                seg[i + 1][j + 1] = a[i][j];
            }
        }
        for (int i = 0; i < h + 1; i++) {
            for (int j = 0; j < w; j++) {
                seg[i][j + 1] += seg[i][j];
            }
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w + 1; j++) {
                seg[i + 1][j] += seg[i][j];
            }
        }
    }

    // [lx, rx) x [ly, ry)
    T sum(int lx, int ly, int rx, int ry) {
        assert(0 <= lx and lx <= rx and rx <= h);
        assert(0 <= ly and ly <= ry and ry <= w);
        return (seg[rx][ry] - seg[lx][ry] - seg[rx][ly] + seg[lx][ly]);
    }

    // (i, j) \in [lx, rx) x [ly, ry) seg[i][j] += z;
    void imos(int lx, int ly, int rx, int ry, T z = T(1)) {
        assert(0 <= lx and lx <= rx and rx <= h);
        assert(0 <= ly and ly <= ry and ry <= w);
        seg[lx][ly] += z;
        seg[lx][ry] -= z;
        seg[rx][ly] -= z;
        seg[rx][ry] += z;
    }

    void build() {
        for (int i = 0; i < h + 1; i++) {
            for (int j = 0; j < w; j++) {
                seg[i][j + 1] += seg[i][j];
            }
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w + 1; j++) {
                seg[i + 1][j] += seg[i][j];
            }
        }
    }

    // return A[x][y]
    T get(int x, int y) const {
        assert(0 <= x and x < h and 0 <= y and y < w);
        return seg[x][y];
    }

    // output
    friend std::ostream &operator<<(std::ostream &os, const CumulativeSum2D &A) {
        os << "h = " << A.h << ", w = " << A.w << "\n";
        for (int i = 0; i <= A.h; i++) {
            for (int j = 0; j <= A.w; j++) {
                os << A.seg[i][j] << " \n"[j == A.w];
            }
        }
        return os;
    }
};
#line 6 "verify/aoj_dsl/aoj_dsl_5_b.test.cpp"

int main() {
    int N;
    std::cin >> N;
    int M = 1000;
    CumulativeSum2D<int> rui(M, M);
    while (N--) {
        int x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        rui.imos(x1, y1, x2, y2);
    }
    rui.build();
    int ans = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) {
            ans = std::max(ans, rui.get(i, j));
        }
    }
    std::cout << ans << '\n';
    return 0;
}

Back to top page