verify/Datastructure_2dsegtree_add.test.cpp

View this file on GitHub
Last update: 2025-01-10 00:00:54+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/2dsegtree.hpp"



using S = ll;
S op(ll l, ll r) {
    return l + r;
}

S e() {
    return 0LL;
}

int main() {
    int N;
    cin >> N;
    int H = 1000, W = 1000;
    segtree2d<S, op, e> seg(H+2, W+2);

    rep(i, 0, N) {
        int sx, sy, tx, ty;
        cin >> sx >> sy >> tx >> ty;
        tx--, ty--;
        seg.set(ty + 1, tx + 1, seg.get(ty + 1, tx + 1) + 1);
        seg.set(sy, sx, seg.get(sy, sx) + 1);
        seg.set(ty + 1, sx, seg.get(ty + 1, sx) - 1);
        seg.set(sy, tx + 1, seg.get(sy, tx + 1) - 1);
    }

    ll ans = 0;
    rep(i, 0, H) rep(j, 0, W) chmax(ans, seg.prod(0, i+1, 0, j+1));
   
    cout << ans << endl;

}

#line 1 "verify/Datastructure_2dsegtree_add.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/2dsegtree.hpp"
template <class S, S (*op)(S, S), S (*e)()> struct segtree2d {
    int id(int y, int x) {return y * 2 * W + x;} //= y番目のセグ木の、ノードxに対応する添字
    int H, W;
    vec<S> dat;
    bool f;

    segtree2d(int h, int w) {
        f = true;
        H = W = 1;
        while(H < h) H <<= 1;
        while(W < w) W <<= 1;
        dat.resize(4 * H * W, e());
    }

    void preset(int y, int x, S v) {f = false,  dat[id(y + H, x + W)] = v; }

    void build() {
        f = true;
        rep(h, H, 2 * H) {
            rrep(w, 1, W) {
                dat[id(h, w)] = op(dat[id(h, 2 * w)], dat[id(h, 2 * w + 1)]);
            }
        }
        
        rrep(h, 0, H) {
            rrep(w, 1, 2 * W) {
                dat[id(h, w)] = op(dat[id(h * 2, w)], dat[id(h * 2 + 1, w)]);
            } 
        }
    }

    void set(int y, int x, S v) {
        assert(f);

        y += H, x += W;
        dat[id(y, x)] = v;
        rrep(w, 1, W) {
            dat[id(y, w)] = op(dat[id(y, 2 * w)], dat[id(y, 2 * w + 1)]);
        }

        while(y > 1) {
            y >>= 1;
            for(int j = x; j >= 1; j >>= 1) {
                dat[id(y, j)] = op(dat[id(y * 2, j)] , dat[id(y * 2 + 1, j)]);
            }
        }
    }

    S inner(int h, int l, int r) {
        S sml = e(), smr = e();
        l += W, r += W;
        while(l < r) {
            if(l & 1) sml = op(sml, dat[id(h, l++)]);
            if(r & 1) smr = op(dat[id(h, --r)], smr);
            l >>= 1, r >>= 1;
        }
        return op(sml, smr);
    }

    S prod(int sy, int ty, int sx, int tx) {
        assert(f);

        S sml = e(), smr = e();
        sy += H, ty += H;
        while(sy < ty) {
            if(sy & 1) sml = op(sml, inner(sy++, sx, tx));
            if(ty & 1) smr = op(inner(--ty, sx, tx), smr);
            sy >>= 1, ty >>= 1;
        }
        return op(sml, smr);
    }

    S get(int y, int x) {
        return dat[id(y + H, x + W)];
    }
};
/*
@brief 2次元セグメント木
@docs doc/2dseg_small.md
*/
#line 4 "verify/Datastructure_2dsegtree_add.test.cpp"



using S = ll;
S op(ll l, ll r) {
    return l + r;
}

S e() {
    return 0LL;
}

int main() {
    int N;
    cin >> N;
    int H = 1000, W = 1000;
    segtree2d<S, op, e> seg(H+2, W+2);

    rep(i, 0, N) {
        int sx, sy, tx, ty;
        cin >> sx >> sy >> tx >> ty;
        tx--, ty--;
        seg.set(ty + 1, tx + 1, seg.get(ty + 1, tx + 1) + 1);
        seg.set(sy, sx, seg.get(sy, sx) + 1);
        seg.set(ty + 1, sx, seg.get(ty + 1, sx) - 1);
        seg.set(sy, tx + 1, seg.get(sy, tx + 1) - 1);
    }

    ll ans = 0;
    rep(i, 0, H) rep(j, 0, W) chmax(ans, seg.prod(0, i+1, 0, j+1));
   
    cout << ans << endl;

}