CCO '13 P4 - A Romantic Movie Outing

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type
Canadian Computing Olympiad: 2013 Day 2, Problem 1

Brian the Computer Science Nerd is going on a date with his girlfriend, Anatevka! His romantic location of choice is a movie theatre - but not an IMAX theatre, of course, as that would be far too expensive.

This theatre has 10^9 rows of 1\,000 seats each, which are initially empty. The rows are numbered 1 \dots 10^9 starting from the one closest to the screen, and the seats in each row are numbered 1 \dots 1\,000 from left to right. Seat c in row r is denoted as seat (r,c). Seats in rows 1 \dots L (1 \le L \le 1\,000) are considered to be close to the screen, while seats in further rows are considered to be far.

Over the course of T (1 \le T \le 500\,000) minutes before the movie starts, a number of events occur. During the i-th minute, either a person enters and sits in the empty seat (R_i,C_i), the person sitting in the occupied seat (R_i,C_i) leaves, or Anatevka suggests that she and Brian take seats (R_i,C_i) and (R_i,C_i + 1). The type of the i-th event is represented by the character E_i, with E_i = E indicating a person entering, E_i = L indicating a person leaving, and E_i = S indicating a seating suggestion. All seats involved in the events are valid seats inside the theatre, and every seat that Anatevka suggests will be close, as she believes that they're the best.

Every time Anatevka makes a suggestion, Brian must, of course, analyze its quality. If either of the two seats she suggests is already occupied, he should explain to her that her recommendation is invalid with a simple No. Otherwise, he'd like to calculate the total inconvenience of both seats in such an arrangement. The inconvenience of sitting in seat (r,c) is the number of occupied seats in its field of vision, excluding itself. The field of vision of seat (r,c) includes all seats which are no further than it from seat (1,c) by Manhattan distance (i.e., Manhattan distance between (x_1,y_1) and (x_2,y_2) is |x_1 - x_2| + |y_1 - y_2|). as shown below (with the S representing a suggested seat, and an F representing a seat within its field of vision:

      S      
    F F F    
  F F F F F  
F F F F F F F

After all the events have taken place, the movie is about to start, and a final decision must be made on where to sit - and Brian will handle that. He conclude that seats that are far are clearly superior (as they offer a broader view of the screen), and he knows that the point of going to the movies is to have an optimal viewing experience, so selecting two adjacent seats is cetainly not mandatory. As such, he'd like to determine the minimum total inconvenience for any two far unoccupied seats in the theatre. Note that, if one of the chosen seats is in the other's field of vision, this does not count toward its inconvenience - it's only determined by other people sitting in the theatre.

Input Specification

The first line of each test case contains two integers, L (1 \le L \le 1\,000) and T (1 \le T \le 500\,000).

The next T lines each contain one character, E_i where E_i \in \{ E, L, S \}, and two integers, R_i and C_i, for i = 1 \dots T (1 \le R_i \le 10^9; 1 \le C_i \le 1\,000).

For test cases worth 20\% of the points, you may assume L \le 100 and T \le 400.

For test cases worth 60\% of the points, you may assume L \le 500 and T \le 50\,000.

Output Specification

For each of Anatevka's suggestions (i.e. when E_i = S in the input), output the string No if the suggestion is invalid; otherwise, output the total inconvenience of the two suggested seats.

The last line of output should contain the minimum total inconvenience of any pair of far, unoccupied seats.

Sample Input

3 7
E 1 2
E 2 5
S 3 4
E 2 3
L 2 5
S 1 3
S 2 2

Output for Sample Input

3
0
No
0

Explanation of Output for Sample Input

When Anatevka makes her first suggestion, the front 3 rows and leftmost 5 columns of the theatre look as follows (where a P represents a person, and an S represents one of the suggested seats)

      S S
        P
  P      

The second suggestion is shown below:

         
    P    
  P S S  

These two seats aren't obstructed by any people, so their total inconvenience is 0. The final suggestion is invalid, as one of its two seats (seat (2,3)) is already occupied.

Finally, Brian can easily select two far seats which each have inconvenience 0, as the theatre has 10^9 - 3 far rows with 1\,000 seats each, and most are far from the two people setting in the theatre after the last event. For example, he might choose to take seat (4,6), while recommending that Anatevka enjoy the view from seat (100,1\,000).


Comments


  • 5
    Riolku  commented on Jan. 2, 2019, 7:09 p.m.

    Hint

    Which data structure do we need for this problem?


  • 1
    account_disabled  commented on Jan. 29, 2018, 5:19 p.m.

    Question

    Could someone please explain to me how the Field of View works? How is (1,2) in the FOV of (3,5) but (2,5) is not in the FOV of (3,4) ???? The problem description of manhattan distance does not make sense to me, I have looked at what manhattan distance is but I still dont get it


  • 6
    Phoenix1369  commented on Oct. 29, 2016, 12:04 p.m. edit 2

    Fixed the second image which corresponds to Anatevka's first suggestion.

    Also, fixed invald, as was pointed out by d in his profile.


  • 6
    kobortor  commented on Aug. 28, 2015, 1:46 p.m. edited

    http://wcipeg.com/problem/ccc13s2p4

    This theatre has 10^9 rows of 1000 seats each, which are initially empty. The rows are numbered 1..10^9 starting from the one closest to the screen, and the seats in each row are numbered 1..1000 from left to right. Seat c in row r is denoted as seat (r,c). Seats in rows 1..L (1 ≤ L ≤ 1000) are considered to be “close” to the screen, while seats in further rows are considered to be “far”.

    • -3
      FatalEagle  commented on Aug. 28, 2015, 3:06 p.m.

      Fixed.


      • 5
        kobortor  commented on Aug. 28, 2015, 3:44 p.m.

        Also I'm confused, if Anatevka first suggested 3, 4 then why is the first picture showing spots 3, 3 and 3, 4? Shouldn't it be 3, 4 and 3, 5?


        • -9
          FatalEagle  commented on Aug. 28, 2015, 4:12 p.m.

          This comment is hidden due to too much negative feedback. Click here to view it.