verify/Datastructure_imos2d.test.cpp

View this file on GitHub
Last update: 2025-02-19 15:03:47+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B&lang=ja

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B&lang=ja"
#include "../Utility/template.hpp"
#include "../Datastructure/imos2d.hpp"

int main() { 
    int n;
    cin >> n;
    imos2d<ll> sum(1001, 1001);

    rep(i, 0, n) {
        int sx, sy, tx, ty;
        cin >> sx >> sy >> tx >> ty;
        sum.imos_add(sy, ty, sx, tx, 1);
    }

    sum.build();
    int ans = 0;
    rep(i, 0, 1001) {
        rep(j, 0, 1001){ 
            chmax(ans, sum.imos_get(i, j));
        }
    }

    cout << ans << endl;

}

#line 1 "verify/Datastructure_imos2d.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B&lang=ja"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/imos2d.hpp"
TT struct imos2d {
    int h, w;
    vec<vec<T>> dat;
    bool f = false;

    imos2d(int h = 0, int w = 0) : h(h), w(w) {
        dat = vec<vec<T>>(h, vec<T>(w, T()));
    }

    void imos_add(int i, int j, T x) {
        assert(f == false);
        imos_add(i, i + 1, j, j + 1, x);
    }

    void imos_add(int sy, int ty, int sx, int tx, T x) {
        assert(f == false);
        if (sx >= tx || sy >= ty) return;
        dat[sy][sx] += x;
        if (ty < h) dat[ty][sx] -= x;
        if (tx < w) dat[sy][tx] -= x;
        if (tx < w && ty < h) dat[ty][tx] += x;
    }

    void build() {
        rep(i, 0, h) {
            rep(j, 0, w - 1) { dat[i][j + 1] += dat[i][j]; }
        }
        rep(j, 0, w) {
            rep(i, 0, h - 1) { dat[i + 1][j] += dat[i][j]; }
        }
        f = true;
    }

    T imos_get(int i, int j) { return dat[i][j]; }
};
/*
@brief 2次元imos法

*/
#line 4 "verify/Datastructure_imos2d.test.cpp"

int main() { 
    int n;
    cin >> n;
    imos2d<ll> sum(1001, 1001);

    rep(i, 0, n) {
        int sx, sy, tx, ty;
        cin >> sx >> sy >> tx >> ty;
        sum.imos_add(sy, ty, sx, tx, 1);
    }

    sum.build();
    int ans = 0;
    rep(i, 0, 1001) {
        rep(j, 0, 1001){ 
            chmax(ans, sum.imos_get(i, j));
        }
    }

    cout << ans << endl;

}