test/atcoder-abc106-d.test.cpp

View this file on GitHub
Last update: 2021-05-27 02:04:57+09:00
Link: View error logs on GitHub Actions

Depends on

datastructure/CumulativeSum2D.hpp

Code

#define IGNORE

#include <iostream>
#include <vector>
#include "../datastructure/CumulativeSum2D.hpp"

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

  int N, M, Q; 
  std::cin >> N >> M >> Q;
  CumulativeSum2D<int> grid(500,500);
  for(int i=0; i<M; i++) {
    int l, r; std::cin >> l >> r;
    l--; r--;
    grid.add(l, r, 500, 500, 1);
  }
  grid.build();

  for(int i=0; i<Q; i++) {
    int p, q; std::cin >> p >> q;
    p--; 
    std::cout << grid(p, p, q, q) << '\n';
  }
  
  return 0;
}

#line 1 "test/atcoder-abc106-d.test.cpp"
#define IGNORE

#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 6 "test/atcoder-abc106-d.test.cpp"

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

  int N, M, Q; 
  std::cin >> N >> M >> Q;
  CumulativeSum2D<int> grid(500,500);
  for(int i=0; i<M; i++) {
    int l, r; std::cin >> l >> r;
    l--; r--;
    grid.add(l, r, 500, 500, 1);
  }
  grid.build();

  for(int i=0; i<Q; i++) {
    int p, q; std::cin >> p >> q;
    p--; 
    std::cout << grid(p, p, q, q) << '\n';
  }
  
  return 0;
}