Contest.uni-smr.ac.ru :: соревнования по программированию

# Problem E for Train 2

Задачу добавил: elena

Успешно сдано решений: 6

Problem E. Enormous spiral
Author: A. Klenin

Input file: input.txt     Time limit: 3 sec
Output file: output.txt     Memory limit: 64 Mb

Statement

Consider an infinite plane divided into square cells with the side of 1. The spiral starts at cell (0, 0) and consists of N straight segments. First segment runs from the starting cell in the direction of x axis, each following segment takes a 90° (pi/2) turn to the right. Segment number i contains exactly ai cells.

Segments do not overlap except at joint cells, which are treated as belonging to both adjacent segments.

A square window on the plane consists of S X S cells and is defined by coordinates of top left cell (x, y) (y axis is directed upwards).

Your program will be given coordinates of K square windows, and must determine, for each window, the number of cells inside it belonging to the spiral.

For example, a spiral below is defined by input of sample test 3. Cells marked with 'x' are inside the first window from the same test.

== pic E ==

Input file format
Input file contains numbers N K S followed by N integers ai, and then by K coordinates xi yi.

Output file format
Output file must contain K numbers — cell counts for each window.

Constraints
2 <= ai <= 10^9, a_(i-1) < a_(i+1), 1 <= N <= 10^6, -10^9 <= xi, yi <= 10^9, 1 <= K <= 10000, 1 <= S <= 100

Sample tests
Sample input 1
1 1 10
100
0 0
Sample output 1
10

Sample input 2
2 1 10
100 1000
1 -1
Sample output 2
0

Sample input 3
4 3 3
4 3 6 4
-1 0
0 0
1 0
Sample output 3
5 6 7