Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anmichi/Library

:heavy_check_mark: test/2DBIT.test.cpp

Depends on

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 :heavy_check_mark: AC 19 ms 7 MB
g++ 00_sample_01.in :heavy_check_mark: AC 19 ms 7 MB
g++ 00_sample_02.in :heavy_check_mark: AC 19 ms 7 MB
g++ 01_small_00.in :heavy_check_mark: AC 20 ms 7 MB
g++ 01_small_01.in :heavy_check_mark: AC 19 ms 7 MB
g++ 01_small_02.in :heavy_check_mark: AC 20 ms 7 MB
g++ 02_minimum_00.in :heavy_check_mark: AC 20 ms 7 MB
g++ 02_minimum_01.in :heavy_check_mark: AC 19 ms 7 MB
g++ 02_minimum_02.in :heavy_check_mark: AC 19 ms 7 MB
g++ 02_minimum_03.in :heavy_check_mark: AC 19 ms 7 MB
g++ 03_rand_00.in :heavy_check_mark: AC 19 ms 7 MB
g++ 03_rand_01.in :heavy_check_mark: AC 19 ms 7 MB
g++ 03_rand_02.in :heavy_check_mark: AC 20 ms 7 MB
g++ 03_rand_03.in :heavy_check_mark: AC 20 ms 7 MB
g++ 04_medium_00.in :heavy_check_mark: AC 20 ms 7 MB
g++ 04_medium_01.in :heavy_check_mark: AC 19 ms 7 MB
g++ 04_medium_02.in :heavy_check_mark: AC 19 ms 7 MB
g++ 04_medium_03.in :heavy_check_mark: AC 19 ms 7 MB
g++ 05_large_00.in :heavy_check_mark: AC 19 ms 7 MB
g++ 05_large_01.in :heavy_check_mark: AC 19 ms 7 MB
g++ 05_large_02.in :heavy_check_mark: AC 20 ms 7 MB
g++ 05_large_03.in :heavy_check_mark: AC 20 ms 7 MB
g++ 06_corner_00.in :heavy_check_mark: AC 26 ms 7 MB
g++ 06_corner_01.in :heavy_check_mark: AC 26 ms 7 MB
g++ 06_corner_02.in :heavy_check_mark: AC 28 ms 7 MB
g++ 06_corner_03.in :heavy_check_mark: AC 33 ms 7 MB
g++ 06_corner_04.in :heavy_check_mark: AC 29 ms 7 MB
g++ 07_corner_fit_00.in :heavy_check_mark: AC 45 ms 7 MB
g++ 07_corner_fit_01.in :heavy_check_mark: AC 50 ms 7 MB
g++ 08_overlaped_00.in :heavy_check_mark: AC 47 ms 7 MB
clang++ 00_sample_00.in :heavy_check_mark: AC 20 ms 7 MB
clang++ 00_sample_01.in :heavy_check_mark: AC 20 ms 7 MB
clang++ 00_sample_02.in :heavy_check_mark: AC 20 ms 7 MB
clang++ 01_small_00.in :heavy_check_mark: AC 19 ms 7 MB
clang++ 01_small_01.in :heavy_check_mark: AC 19 ms 7 MB
clang++ 01_small_02.in :heavy_check_mark: AC 19 ms 7 MB
clang++ 02_minimum_00.in :heavy_check_mark: AC 19 ms 7 MB
clang++ 02_minimum_01.in :heavy_check_mark: AC 20 ms 7 MB
clang++ 02_minimum_02.in :heavy_check_mark: AC 20 ms 7 MB
clang++ 02_minimum_03.in :heavy_check_mark: AC 19 ms 7 MB
clang++ 03_rand_00.in :heavy_check_mark: AC 20 ms 7 MB
clang++ 03_rand_01.in :heavy_check_mark: AC 19 ms 7 MB
clang++ 03_rand_02.in :heavy_check_mark: AC 19 ms 7 MB
clang++ 03_rand_03.in :heavy_check_mark: AC 19 ms 7 MB
clang++ 04_medium_00.in :heavy_check_mark: AC 19 ms 7 MB
clang++ 04_medium_01.in :heavy_check_mark: AC 19 ms 7 MB
clang++ 04_medium_02.in :heavy_check_mark: AC 19 ms 7 MB
clang++ 04_medium_03.in :heavy_check_mark: AC 19 ms 7 MB
clang++ 05_large_00.in :heavy_check_mark: AC 19 ms 7 MB
clang++ 05_large_01.in :heavy_check_mark: AC 20 ms 7 MB
clang++ 05_large_02.in :heavy_check_mark: AC 20 ms 7 MB
clang++ 05_large_03.in :heavy_check_mark: AC 20 ms 7 MB
clang++ 06_corner_00.in :heavy_check_mark: AC 26 ms 7 MB
clang++ 06_corner_01.in :heavy_check_mark: AC 27 ms 7 MB
clang++ 06_corner_02.in :heavy_check_mark: AC 26 ms 7 MB
clang++ 06_corner_03.in :heavy_check_mark: AC 33 ms 7 MB
clang++ 06_corner_04.in :heavy_check_mark: AC 29 ms 7 MB
clang++ 07_corner_fit_00.in :heavy_check_mark: AC 44 ms 7 MB
clang++ 07_corner_fit_01.in :heavy_check_mark: AC 48 ms 7 MB
clang++ 08_overlaped_00.in :heavy_check_mark: AC 48 ms 7 MB
Back to top page