33OJ
登录 注册

#P17500. [ICPC 2026 Wuhan I] Rectangle Cutting

[ICPC 2026 Wuhan I] Rectangle Cutting

Problem Description

Yachiyo has a rectangle in the first quadrant of the Cartesian coordinate plane. The lower-left corner of the rectangle is at the origin (0,0)(0,0), and the upper-right corner is at (n,m)(n,m). In other words, the two sides of the rectangle are aligned with the xx-axis and the yy-axis, with lengths nn and mm along the xx- and yy-directions, respectively.

Yachiyo decides to make qq cuts on this rectangle. Specifically, there are two kinds of cuts:

  • Horizontal cut: given a positive integer kk, cut along the line y=ky=k.
  • Vertical cut: given a positive integer kk, cut along the line x=kx=k.

Each cut goes through the entire region, further dividing the existing rectangles into more smaller rectangles.

Yachiyo wants to know, after each cut is completed, what the maximum area among all the currently divided small rectangles is.

Input Format

The first line contains three integers n,m,qn,m,q (1≤n,m≤1091 \le n,m \le 10^9, 1≤q≤5×1051 \le q \le 5\times10^5), representing the horizontal length, vertical length, and the number of cuts of the initial rectangle, respectively.

The next qq lines each contain two integers op,kop,k, describing one cut operation:

  • If op=1op=1, it means a vertical cut is performed, and the given integer kk (1≤k<n1 \le k<n) indicates cutting along the line x=kx=k.
  • If op=2op=2, it means a horizontal cut is performed, and the given integer kk (1≤k<m1 \le k<m) indicates cutting along the line y=ky=k.

It is guaranteed that Yachiyo will never cut at the same position twice (that is, all cutting lines are distinct).

Output Format

Output qq lines. The ii-th line should contain one integer, representing the maximum area among all small rectangles after the ii-th cut.

5 3 3
1 1
1 4
2 2
12
9
6

Hint

:::align{center}

Pic. 1: Sample explanation :::