Indian Computing Olympiad

Training Material


Range Queries→Artemis (IOI 2004)

Zeus gave Artemis, the goddess of the wilderness, a rectangular area for growing a forest. With the left side of the area as a segment of the positive y-axis and the bottom side as a segment of the positive x-axis, and (0,0) the left bottom corner of the area, Zeus told Artemis to only plant trees only on integer coordinate points in the area. Artemis liked the forest to look natural, and therefore planted trees in such a way that a line connecting two trees was never parallel to x-axis or y-axis. At times, Zeus wants Artemis to cut trees for him. The trees are to be cut as follows:

  1. Zeus wants at least a given number T of trees to be cut for him.

  2. To get a rectangular football pitch for future football success, Artemis is to cut all trees within a rectangular area, and no trees outside of it.

  3. The sides of this rectangular area are to be parallel to x-axis and y-axis.

  4. Two opposite corners of the area trees must be located on trees and therefore those corner trees are also cutstand in two opposite corners of the area (and are included in it).

As Artemis likes the trees, she wants to fulfill these conditions whilst cutting as few trees as possible. You are to write a program that, given information of on the forest and the minimum number T of trees to be cut, selects an area for cutting trees for Artemis.

Limits:

  • Grid is 64000 × 64000
  • Number of trees is 10000 (was 20000 in IOI, but this seems wrong!)
  • Memory is 16MB

Solution