test/aoj-dsl-5-b.test.cpp

• View this file on GitHub
• Last update: 2021-05-27 02:08:05+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B

Depends on

• datastructure/CumulativeSum2D.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B"
#include <iostream>
#include <vector>
#include "../datastructure/CumulativeSum2D.hpp"

int main(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int N; 
  std::cin >> N;
  CumulativeSum2D<int> grid(1000,1000);
  for(int i=0; i<N; i++) {
    int sx, sy, ex, ey; std::cin >> sx >> sy >> ex >> ey;
    grid.add(sy, sx, ey, ex, 1);
  }
  grid.build();
  int ans = 0;
  for(int i=0; i<=1000; i++) {
    for(int j=0; j<=1000; j++) {
      ans = std::max(ans, grid(0, 0, i, j));
    }
  }
  std::cout << ans << '\n';
  return 0;
}

#line 1 "test/aoj-dsl-5-b.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_5_B"
#include <iostream>
#include <vector>
#line 2 "datastructure/CumulativeSum2D.hpp"
#include <cassert>
#line 4 "datastructure/CumulativeSum2D.hpp"
template<typename T>
struct CumulativeSum2D{
  int H, W;
  std::vector<std::vector<T>> data;
 
  CumulativeSum2D(int h, int w): H(h), W(w){
    data.resize(H+10, std::vector<T>(W+10));
  }
 
  // [sy, sx], [ey, ex]
  void add(int sy, int sx, int ey, int ex, T x) {
    sy++; sx++; ey++; ex++;
    data[sy][sx] += x;
    data[ey][ex] += x;
    data[sy][ex] -= x;
    data[ey][sx] -= x;
  } 
  
  void build() {
    for(int i=1; i<=H; i++) for(int j=1; j<=W; j++) {
      data[i][j] += data[i][j-1] + data[i-1][j] - data[i-1][j-1];
    }
  }

  // (sy, sx), [ey, ex]
  inline T operator()(int sy, int sx, int ey, int ex) { 
    return data[ey][ex] - data[sy][ex] - data[ey][sx] + data[sy][sx];
  }
};
#line 5 "test/aoj-dsl-5-b.test.cpp"

int main(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int N; 
  std::cin >> N;
  CumulativeSum2D<int> grid(1000,1000);
  for(int i=0; i<N; i++) {
    int sx, sy, ex, ey; std::cin >> sx >> sy >> ex >> ey;
    grid.add(sy, sx, ey, ex, 1);
  }
  grid.build();
  int ans = 0;
  for(int i=0; i<=1000; i++) {
    for(int j=0; j<=1000; j++) {
      ans = std::max(ans, grid(0, 0, i, j));
    }
  }
  std::cout << ans << '\n';
  return 0;
}

Back to top page