Woburn Challenge 2015-16 Round 2 - Senior Division

Problem II: Attack of the Clones

“You know I don't like it when you do that.”
“Sorry, master. I forgot that you don't like coding.”
“I don't mind coding, but what you're doing is suicide!”

Upon thwarting an attempt on Senator Amidala's life, Obi-Wan Kenobi and Anakin Skywalker must pursue the bounty hunter Zam Wesell through the bustling streets of Coruscant in order to apprehend and question her. Unfortunately, they've already lost her trail! Fortunately, they have some ideas of where she might be hiding.

The city of Coruscant is laid out in a regular grid of intersections. There are many parallel avenues running North-South, numbered from West to East starting from 1. Similarly, there are many parallel streets running East-West, numbered from North to South starting from 1. The position where street s and avenue a intersect can be denoted as (s, a).

All of the streets and avenues are one-way, and even in this emergency, the Jedi must respect the law. Every avenue may only be travelled along towards the South. However, the directions of the streets alternate – every odd-numbered street may only be travelled along towards the East, while every even-numbered street may only be travelled along towards the West. It takes 1 minute to travel from a certain intersection to an adjacent one (either to the South, East, or West, while obeying the traffic laws).

The Jedi are currently in the Senate building at intersection (1, 1). There are N (1 ≤ N ≤ 200,000) potential locations at which Zam might be hiding, numbered from 1 to N in decreasing order of likelihood, with the i-th one being intersection (S_i, A_i) (1 ≤ S_i, A_i ≤ 40,000). None of the N locations is (1, 1), and no two of them are at the same intersection.

A decision must be made on how many of the locations to try. As such, for every i in the range 1..N, you must determine the minimum amount of time (in minutes) that it would take for the Jedi to theoretically visit all of the first i locations (in any order), starting from (1, 1).

In test cases worth 75% of the points, N ≤ 2000.
In a subset of those cases worth 30% of the points, N ≤ 100, S_i ≤ 100, and A_i ≤ 100.

Input Format

The first line of input consists of a single integer N.
The next N lines each consist of two space-separated integers S_i and A_i, for i = 1..N.

Output Format

The output should consist of N lines, where the i-th line is a single integer representing the minimum amount of time (in minutes) that it would take for the Jedi to theoretically visit all of the first i locations (in any order), starting from (1, 1).

Sample Input

7
5 3
5 2
2 4
6 1
1 4
3 1
6 6

Sample Output

6
6
10
13
13
15
21

Explanation

The following diagram depicts the scenario in the sample input. Green represents the senate building, blue represents a normal intersection, and yellow represents potential locations at which Zam might be hiding.

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 3.00s
Memory Limit: 16M
Added: Dec 12, 2015
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

To make this problem slightly fairer to languages such as Java, we've decided to raise the time limit of the judge version of this problem. All submissions are rejudged on the main site.
This change will not affect the in-contest results in any way (and in fact couldn't have, because none of the failed in-contest submissions got AC after the rejudging anyway).