test/aoj/dsl/dsl_5_b.test.cpp

• View this file on GitHub
• Last update: 2024-11-15 16:06:01+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B

Depends on

• Binary Indexed Tree 2D (lib/data_structure/binary_indexed_tree_2d.hpp)

Code

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

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

using namespace std;

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

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

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

/**
 * @brief Binary Indexed Tree 2D
 * @docs docs/data_structure/binary_indexed_tree_2d.md
 */

#include <vector>
#include <cassert>

template <typename T>
struct BinaryIndexedTree2D{
    int H, W;
    std::vector<std::vector<T>> BIT;
    BinaryIndexedTree2D(const int _H, const int _W) : H(_H + 1), W(_W + 1){
        BIT.resize(H + 3, std::vector<T>(W + 3, 0));
    }

    void add(const int x, const int y, const T v){
        assert(0 <= x && x < H && 0 <= y && y < W);
        for(int a = x + 1; a <= H; a += a & -a){
            for(int b = y + 1; b <= W; b += b & -b){
                BIT[a][b] += v;
            }
        }
    }

    void imos(const int x1, const int y1, const int x2, const int y2, const T v){
        add(x1, y1, v);
        add(x1, y2 + 1, -v);
        add(x2 + 1, y1, -v);
        add(x2 + 1, y2 + 1, v);
    }

    T sum(const int x, const int y){
        assert(x < H && y < W);
        if(x < 0 || y < 0) return 0;
        T res = 0;
        for(int a = x + 1; a > 0; a -= a & -a){
            for(int b = y + 1; b > 0; b -= b & -b){
                res += BIT[a][b];
            }
        }
        return res;
    }

    T sum(const int x1, const int y1, const int x2, const int y2){
        if(x1 > x2 || y1 > y2) return T(0);
        return sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) + sum(x1 - 1, y1 - 1);
    }
};
#line 5 "test/aoj/dsl/dsl_5_b.test.cpp"

using namespace std;

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

Back to top page