This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#define PROBLEM \ "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B" #include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; #include "data-structure/fenwick2d.hpp" signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); const int N = 1001; int n; cin >> n; fenwick2d<int> f(N, N); for (int i = 0; i < n; ++i) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; f.add(x1, y1, x2, y2, 1); } int ans = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { ans = max(ans, f.sum(i + 1, j + 1)); } } cout << ans << '\n'; }
#line 1 "data-structure/test/The_Maximum_Number_of_Overlaps.test.cpp" #define PROBLEM \ "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B" #include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; #line 1 "data-structure/fenwick.hpp" template <typename T> struct fenwick { fenwick(int n) : n(n), f(n + 1) {} // a[u] += val void add(int u, T val) { assert(0 <= u && u < n); ++u; while (u <= n) f[u] += val, u += u & -u; } // return the sum of [0, u) T sum(int u) const { assert(0 <= u && u <= n); T res = 0; while (u) res += f[u], u -= u & -u; return res; } // return the sum of [l, r) T sum(int l, int r) const { assert(0 <= l && l <= r && r <= n); if (l == r) return 0; return sum(r) - sum(l); } void reset() { fill(f.begin(), f.end(), T(0)); } int n; vector<T> f; }; #line 2 "data-structure/fenwick2d.hpp" template <class T> struct fenwick2d { int n, m; vector<fenwick<T>> f; fenwick2d(int n, int m) : n(n), m(m), f(n + 1, fenwick<T>(m)) {} void add(int x, int y, T v) { assert(0 <= x && x < n && 0 <= y && y < m); ++x; while (x <= n) f[x].add(y, v), x += x & -x; } // add v to [x1, x2) x [y1, y2) void add(int x1, int y1, int x2, int y2, T v) { add(x1, y1, v); add(x1, y2, -v); add(x2, y1, -v); add(x2, y2, v); } // sum of [0, x) * [0, y) T sum(int x, int y) { T res = 0; while(x) res += f[x].sum(y), x -= x & -x; return res; } // sum of [x1, x2) * [y1, y2) T sum(int x1, int y1, int x2, int y2) { return sum(x2, y2) - sum(x1, y2) - sum(x2, y1) + sum(x1, y1); } }; #line 12 "data-structure/test/The_Maximum_Number_of_Overlaps.test.cpp" signed main() { ios::sync_with_stdio(false); cin.tie(nullptr), cin.exceptions(cin.failbit); const int N = 1001; int n; cin >> n; fenwick2d<int> f(N, N); for (int i = 0; i < n; ++i) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; f.add(x1, y1, x2, y2, 1); } int ans = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { ans = max(ans, f.sum(i + 1, j + 1)); } } cout << ans << '\n'; }