test/2DBIT.test.cpp

• View this file on GitHub
• Last update: 2025-07-04 15:57:54+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/DSL_5_B

Depends on

• 2DBIT.cpp

Code

#include "../2DBIT.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DSL_5_B
template <class T, class U>
inline bool chmax(T &a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    const int n = 1001;
    BIT2D<int> bit(n, n);
    int q;
    cin >> q;
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a++, b++, c++, d++;
        //(a,c],(b,d]
        bit.add(c, d, 1);
        bit.add(a, d, -1);
        bit.add(c, b, -1);
        bit.add(a, b, 1);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            chmax(ans, bit.sum(i, j));
        }
    }
    cout << ans << endl;
}

#line 1 "2DBIT.cpp"
#include <bits/stdc++.h>
using namespace std;
template <class T>
struct BIT2D {
    int n, m;
    vector<vector<T>> bit;
    BIT2D(int n, int m) : n(n), m(m) { bit.resize(n + 1, vector<T>(m + 1)); }
    void add(int a, int b, T w) {
        for (int x = a; x <= n; x += x & -x) {
            for (int y = b; y <= m; y += y & -y) {
                bit[x][y] += w;
            }
        }
    }
    T sum(int a, int b) {
        T res = 0;
        for (int x = a; x > 0; x -= x & -x) {
            for (int y = b; y > 0; y -= y & -y) {
                res += bit[x][y];
            }
        }
        return res;
    }
    T sum(int a, int b, int c, int d) {
        //[a,c],[b,d]
        return sum(c, d) - sum(a - 1, d) - sum(c, b - 1) + sum(a - 1, b - 1);
    }
};
#line 2 "test/2DBIT.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DSL_5_B
template <class T, class U>
inline bool chmax(T &a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    const int n = 1001;
    BIT2D<int> bit(n, n);
    int q;
    cin >> q;
    while (q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a++, b++, c++, d++;
        //(a,c],(b,d]
        bit.add(c, d, 1);
        bit.add(a, d, -1);
        bit.add(c, b, -1);
        bit.add(a, b, 1);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            chmax(ans, bit.sum(i, j));
        }
    }
    cout << ans << endl;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	19 ms	7 MB
g++	00_sample_01.in	AC	19 ms	7 MB
g++	00_sample_02.in	AC	19 ms	7 MB
g++	01_small_00.in	AC	20 ms	7 MB
g++	01_small_01.in	AC	19 ms	7 MB
g++	01_small_02.in	AC	20 ms	7 MB
g++	02_minimum_00.in	AC	20 ms	7 MB
g++	02_minimum_01.in	AC	19 ms	7 MB
g++	02_minimum_02.in	AC	19 ms	7 MB
g++	02_minimum_03.in	AC	19 ms	7 MB
g++	03_rand_00.in	AC	19 ms	7 MB
g++	03_rand_01.in	AC	19 ms	7 MB
g++	03_rand_02.in	AC	20 ms	7 MB
g++	03_rand_03.in	AC	20 ms	7 MB
g++	04_medium_00.in	AC	20 ms	7 MB
g++	04_medium_01.in	AC	19 ms	7 MB
g++	04_medium_02.in	AC	19 ms	7 MB
g++	04_medium_03.in	AC	19 ms	7 MB
g++	05_large_00.in	AC	19 ms	7 MB
g++	05_large_01.in	AC	19 ms	7 MB
g++	05_large_02.in	AC	20 ms	7 MB
g++	05_large_03.in	AC	20 ms	7 MB
g++	06_corner_00.in	AC	26 ms	7 MB
g++	06_corner_01.in	AC	26 ms	7 MB
g++	06_corner_02.in	AC	28 ms	7 MB
g++	06_corner_03.in	AC	33 ms	7 MB
g++	06_corner_04.in	AC	29 ms	7 MB
g++	07_corner_fit_00.in	AC	45 ms	7 MB
g++	07_corner_fit_01.in	AC	50 ms	7 MB
g++	08_overlaped_00.in	AC	47 ms	7 MB
clang++	00_sample_00.in	AC	20 ms	7 MB
clang++	00_sample_01.in	AC	20 ms	7 MB
clang++	00_sample_02.in	AC	20 ms	7 MB
clang++	01_small_00.in	AC	19 ms	7 MB
clang++	01_small_01.in	AC	19 ms	7 MB
clang++	01_small_02.in	AC	19 ms	7 MB
clang++	02_minimum_00.in	AC	19 ms	7 MB
clang++	02_minimum_01.in	AC	20 ms	7 MB
clang++	02_minimum_02.in	AC	20 ms	7 MB
clang++	02_minimum_03.in	AC	19 ms	7 MB
clang++	03_rand_00.in	AC	20 ms	7 MB
clang++	03_rand_01.in	AC	19 ms	7 MB
clang++	03_rand_02.in	AC	19 ms	7 MB
clang++	03_rand_03.in	AC	19 ms	7 MB
clang++	04_medium_00.in	AC	19 ms	7 MB
clang++	04_medium_01.in	AC	19 ms	7 MB
clang++	04_medium_02.in	AC	19 ms	7 MB
clang++	04_medium_03.in	AC	19 ms	7 MB
clang++	05_large_00.in	AC	19 ms	7 MB
clang++	05_large_01.in	AC	20 ms	7 MB
clang++	05_large_02.in	AC	20 ms	7 MB
clang++	05_large_03.in	AC	20 ms	7 MB
clang++	06_corner_00.in	AC	26 ms	7 MB
clang++	06_corner_01.in	AC	27 ms	7 MB
clang++	06_corner_02.in	AC	26 ms	7 MB
clang++	06_corner_03.in	AC	33 ms	7 MB
clang++	06_corner_04.in	AC	29 ms	7 MB
clang++	07_corner_fit_00.in	AC	44 ms	7 MB
clang++	07_corner_fit_01.in	AC	48 ms	7 MB
clang++	08_overlaped_00.in	AC	48 ms	7 MB

Back to top page