Person in Charge

• 035966_L3

Attention

After each output line, use fflush(stdout); / cout.flush(); / cout << endl; to flush the buffer.

You may consider using unsigned short to store elevation data for space optimization.

Problem Background

Sleeping Bear is an adorable little bear who becomes even cuter the more honey it eats. However, each time it collects honey, bees sting its head all over. Today it wants honey again but hopes to avoid stings, so it asks you to design an escape route to evade the bees.

Problem Description

Given a positive integer $k$, representing a $k \times k$ map where each cell has:

• An elevation value (unique integers from $0$ to $k^2-1$);
• Sleeping Bear's possible starting positions (bees are right behind);
• Impassable terrain and lake locations (only by reaching lakes can it avoid stings).

Key conditions:

• Sleeping Bear may start at any position with elevation greater than $x$ and less than $y$;
• All positions with elevation $\le$ $x$ are flooded (lakes);
• All positions with elevation $≥$ $y$ are snow-covered (impassable);
• All positions with elevation between $x$ and $y$ are passable;
• Guaranteed $x < y$.

Over $q$ days (each with different $x,y$ values due to weather), count how many passable positions lack paths to lakes (moving up/down/left/right).

Input Format

First line: $k$ (map size), $q$ (number of queries)

Next $k$ lines: $k$ integers each (map elevations, containing all values $0$ to $k^2-1$)

Next $q$ lines: pairs $x,y$ (guaranteed $x < y$)

Output Format

For each query, output one integer immediately (responses must be online).

Sample

5 4
9 12 21 7 4
22 18 17 13 10
5 23 1 3 19
16 6 20 14 2
0 15 24 11 8
0 15
4 18
11 22
1 14

14
2
0
7

10 10
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99
0 1
1 2
2 3
3 5
5 8
8 13
13 21
21 34
34 55
55 89

0
0
0
0
0
0
0
0
0
0

Sample 1 Explanation

An image is available here. If not visible, download it from the "Attachments" section.

Green positions lack lake access paths, red positions have paths. Thus, the answers are: $14,2,0,7$.

Data Range

• $50\%$ data: $2 \le k \le 10$，$1 \le q \le 100$.
• $100\%$ data: $2 \le k \le 250$，$1 \le q \le 10^5$.
• Elevations are unique permutations of $0$ to $k^2-1$
• Guaranteed $0 ≤ x < y ≤ k^2-1$

Additional Files

Download the files here.

Official Solution

link