Table of Contents

ExplanationImplementation

Official Analysis (C++)

Explanation

The overall approach is to use 2D prefix sums along with some jank combinatorics stuff.

We start by constructing a 2D array aa where a[h][w]a[h][w] contains the area of all rectangles with height hh and width ww exactly.

To get the area of all rectangles that satisfy a certain query, we perform a 2D prefix sum from a[hs+1][ws+1]a[h_s+1][w_s+1] to a[hb−1][wb−1]a[h_b-1][w_b-1] inclusive.

Implementation

Time Complexity: O(D2+n+q)\mathcal{O}(D^2+n+q), where DD is the largest dimension we have to handle.

C++

#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


constexpr int MAX_SIDE = 1000;


int main() {

Java

import java.io.*;
import java.util.*;


public class CountingRectangles {
	private static final int MAX_SIDE = 1000;


	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());
		for (int t = 0; t < testNum; t++) {

Python

Warning!

This solution only runs in time when submitted with PyPy.

MAX_SIDE = 1000


overall_ans = []


for _ in range(int(input())):
	rect_num, query_num = [int(i) for i in input().split()]


	pref = [[0 for _ in range(MAX_SIDE + 1)] for _ in range(MAX_SIDE + 1)]
	for _ in range(rect_num):
		h, w = [int(i) for i in input().split()]

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum