data-structure/test/The_Maximum_Number_of_Overlaps.test.cpp

View this file on GitHub
Last update: 2023-07-25 00:50:50+07:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B

Depends on

Code

#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';
}