Description

There are N bars line up in a row. The height of the i-th bar is h_i, and the width of each bar is 1. Please find the largest rectangle in it. 

Sample test:

Input

The first line has an integer T, means there are T testcases.

The first line of each testcase contains an integer N, and the second line contains N integers h₁ ~ h_N.

1 <= h_i <= 1e9.

1 <= T <= 10.

In testcase 1 ~ 4: 1 <= N <= 1000.

In testcase 5 ~ 8: 1 <= N <= 2e5.

Output

Please print the area of the largest rectangle for each testcase.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are trapped in an $N \times M$ grid-based magical dungeon. The grid consists of empty spaces (.), magical walls (#), a starting point (S), and an exit (E).

You start the journey with $K$ magic points. In each step, you can move to one of the four adjacent cells (up, down, left, right).

• If the target cell is an empty space (.), the start (S), or the exit (E), moving there costs 1 step and 0 magic points.
• If the target cell is a magical wall (#), moving there costs 1 step and 1 magic point to break it. Once broken, you move into that cell.
• If you have 0 magic points, you cannot move into a cell with a magical wall.

Your goal is to find the minimum number of steps required to reach the exit (E). If it is impossible to escape the dungeon, output -1.

Input

The first line contains three integers $N$, $M$, and $K$, separated by spaces.

• $N$: the number of rows in the dungeon.
• $M$: the number of columns in the dungeon.
• $K$: your initial magic points.

The following $N$ lines each contain a string of length $M$ consisting of the characters ., #, S, and E.
It is guaranteed that there is exactly one S and exactly one E in the grid.

Constraints

• $1 \le N, M \le 1000$
• $0 \le K \le 100$

Subtasks

• Testcases 1-3: $N, M \le 100$, $K = 0$
• Testcases 4-6: $N, M \le 100$
• Testcases 7-8: No additional constraints.

 

Output

Print a single integer denoting the minimum number of steps to reach the exit E. If you are unable to reach the exit, print -1.

Hint

Sample 1

If you do not use magic, you must take a long detour around the walls: (0,0) -> (0,1) -> (0,2) -> (0,3) -> (0,4) -> (1,4) -> (2,4) -> (2,3) -> (2,2) -> (2,1) -> (2,0), taking exactly 10 steps.
However, with $K = 1$, you can break the wall at (1,0) and go directly to E at (2,0). The path is (0,0) -> (1,0) -> (2,0), taking only 2 steps.

Sample 2

The exit is completely surrounded by walls, and you have 0 magic points. There is no way to reach it.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In computational geometry, managing the relationship between spatial objects is a fundamental task. In this problem, you are required to implement a Rectangle Algebra System using C++ Classes and Operator Overloading.

Your goal is to treat geometric rectangles as algebraic elements, where the Intersection, Bounding Box, and Scaling operations are represented by standard operators.

1. Geometric Definition

Each rectangle in this system is a Axis-Aligned Bounding Box and is defined by two points (x1 , y1) and (x2 , y2) on its diagonal. You need to implement the constructor to store these information in a useful way.

2. Algebraic Operators

You must overload the following operators to support complex geometric expressions:

 

• Intersection (A & B):

  Returns a new Rectangle representing the overlapping area.

  • Identity Logic: If A and B do not overlap, or one's area is 0, then it should return a zero-area rectangle.

• Modified Union, or Bounding Box (A | B):

  Returns a new Rectangle that is the smallest axis-aligned rectangle containing both A and B.

  • Identity Logic: If A is a zero-area rectangle, then it should return B.

• Scaling (A * multiplier):

  Returns a new Rectangle scaled by the absolute value of the multiplier from its center point. If the multiplier is negative, the width and height of the rectangle should be swapped after scaling.

  • Identity Logic: If A is a zero-area rectangle, it should return a zero-area rectangle.

• Assignment (A = B):

  Ensures that rectangles can be assigned to one another safely.

3. Area Calculation

The system must be able to calculate the area of the resulting rectangle.

Constraints

• 1 <= N <= 100.
• -10⁶ <= x, y <= 10^6​

Testcase Design

• Testcase 1~4: Intersection, Bounding Box
• Testcase 5~6: Intersection, Bounding Box, and Scaling with positive multiplier
• Testcase 7~8: Unlimited

Input

The first line contains an integer N, the number of rectangles.

The next N lines each contain Name x1 y1 x2 y2.

• Name: A unique string ID.

• x1 y1 x2 y2: Coordinates of two opposite corner.

The final line is a space-separated algebraic string. Operators include & (Intersection), | (Bounding Box), and * (Scaling). You must evaluated it from left to right.

Output

A single line containing the area of the final resulting rectangle, with '\n'.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14967.cpp

Partial Judge Header

14967.h

Tags

Discuss