TLE '17 Contest 2 P2 - Unlucky Numbers - Olympiads Online Judge

TLE '17 Contest 2 P2 - Unlucky Numbers

Points: 5 (partial)

Time limit: 2.0s

Python 4.0s

Memory limit: 256M

Author:

ChaSiu

Problem type

The bright red buildings and skies of the University of Fireloo.

The University of Fireloo is about to build a new on-campus residence named University of Fireloo Place (UFP), a village with $N$ $N$ apartment buildings!

Apparently, UFP's architects are quite superstitious, so they believe that the $K$ $K$ distinct numbers $u_1, \dots, u_K$ $u_{1}, \dots, u_{K}$ are "unlucky". As a result, for the $i^\text{th}$ $i^{th}$ apartment building, they want the floors to be numbered from $1$ $1$ to $f_i$ $f_{i}$ inclusive, but removing all floors with unlucky floor numbers.

Now, the architects need your help to determine how many floors each apartment in UFP should really have.

Constraints

$1 \le N \le 1\,000\,000$ $1 \leq N \leq 1 000 000$
$1 \le K \le 500\,000$ $1 \leq K \leq 500 000$
$1 \le f_i \le 1\,000\,000$ $1 \leq f_{i} \leq 1 000 000$ $(i = 1, \dots, N)$ $(i = 1, \dots, N)$
$1 \le u_j \le 1\,000\,000$ $1 \leq u_{j} \leq 1 000 000$ $(j = 1, \dots, K)$ $(j = 1, \dots, K)$

For 20% of the points, $N, f_i, u_j \le 100$ $N, f_{i}, u_{j} \leq 100$ , and $K \le 10$ $K \leq 10$ for all $i$ $i$ and $j$ $j$ .

For an additional 30% of the points, $N, f_i, u_j \le 100\,000$ $N, f_{i}, u_{j} \leq 100 000$ , and $K \le 10\,000$ $K \leq 10 000$ for all $i$ $i$ and $j$ $j$ .

Input Specification

The first line contains $K$ $K$ , the number of unlucky numbers the architects have considered.

The second line contains distinct, space-separated positive integers $u_1, \dots, u_K$ $u_{1}, \dots, u_{K}$ , the unlucky numbers.

The third line contains $N$ $N$ , the number of apartments to be built in UFP.

For the next $N$ $N$ lines, the $i^\text{th}$ $i^{th}$ line contains $f_i$ $f_{i}$ , the top floor number of the $i^\text{th}$ $i^{th}$ apartment. It is guaranteed that no top floor number is an unlucky number.

Output Specification

Output $N$ $N$ lines, where the $i^\text{th}$ $i^{th}$ line contains one integer denoting the actual number of floors the $i^\text{th}$ $i^{th}$ apartment should have.

Sample Input

Copy

Sample Output

Copy

14
12

Comments

0

Tearful commented on Nov. 1, 2017, 11:12 p.m.

Someone please tell me what I can do to make my code run faster :v

1

unsuspiciouscrumpet commented on Nov. 2, 2017, 12:11 a.m.

You need to change your approach to the question since your current time complexity is too large. You can read the editorial for a hint.