test/aoj/dsl_5_b.test.cpp

View this file on GitHub
Last update: 2022-12-29 23:55:31+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/5/DSL_5_B

Depends on

src/dp/imos_2d.hpp

Code

#define PROBLEM                                                                \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/5/DSL_5_B"

#include <bits/stdc++.h>
using namespace std;

#include "../../src/dp/imos_2d.hpp"

int main() {
  int n;
  cin >> n;
  vector<Imos2dInterval<long long>> intervals(n);
  for (int i = 0; i < n; i++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    intervals[i] = {{x1, y1}, {x2, y2}, 1};
  }
  Imos2d<long long> imos(1001, 1001, intervals);
  long long ans = 0;
  for (int x = 0; x < 1001; x++) {
    for (int y = 0; y < 1001; y++) {
      ans = max(ans, imos.get({x, y}));
    }
  }
  cout << ans << endl;
  return 0;
}

#line 1 "test/aoj/dsl_5_b.test.cpp"
#define PROBLEM                                                                \
  "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/5/DSL_5_B"

#include <bits/stdc++.h>
using namespace std;

#line 2 "src/dp/imos_2d.hpp"

#line 4 "src/dp/imos_2d.hpp"
using namespace std;

// x and y is 0-indexed.
struct Imos2dPoint {
  int x, y;
};
// [start, end)
template <typename T> struct Imos2dInterval {
  Imos2dPoint start, end;
  T v;
};

template <typename T> struct Imos2d {
private:
  int h, w;
  vector<vector<T>> s;

public:
  Imos2d(int h, int w, const vector<Imos2dInterval<T>> &intervals)
      : h(h), w(w) {
    s.resize(h + 1, vector<T>(w + 1, 0));
    for (auto interval : intervals) {
      s[interval.start.y][interval.start.x] += interval.v;
      s[interval.start.y][interval.end.x] -= interval.v;
      s[interval.end.y][interval.start.x] -= interval.v;
      s[interval.end.y][interval.end.x] += interval.v;
    }
    for (int y = 0; y < h; ++y)
      for (int x = 0; x < w; ++x) {
        s[y + 1][x] += s[y][x];
      }
    for (int y = 0; y < h; ++y)
      for (int x = 0; x < w; ++x) {
        s[y][x + 1] += s[y][x];
      }
  }

  // x and y is 0-indexed.
  T get(const Imos2dPoint &p) { return s[p.y][p.x]; }
};
#line 8 "test/aoj/dsl_5_b.test.cpp"

int main() {
  int n;
  cin >> n;
  vector<Imos2dInterval<long long>> intervals(n);
  for (int i = 0; i < n; i++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    intervals[i] = {{x1, y1}, {x2, y2}, 1};
  }
  Imos2d<long long> imos(1001, 1001, intervals);
  long long ans = 0;
  for (int x = 0; x < 1001; x++) {
    for (int y = 0; y < 1001; y++) {
      ans = max(ans, imos.get({x, y}));
    }
  }
  cout << ans << endl;
  return 0;
}