TLE '17 Contest 2 P2 - Unlucky Numbers

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Python 4.0s
Memory limit: 256M

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 apartment buildings!

Apparently, UFP's architects are quite superstitious, so they believe that the K distinct numbers u_1, \dots, u_K are "unlucky". As a result, for the i^\text{th} apartment building, they want the floors to be numbered from 1 to 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.


1 \le N \le 1\,000\,000
1 \le K \le 500\,000
1 \le f_i \le 1\,000\,000 (i = 1, \dots, N)
1 \le u_j \le 1\,000\,000 (j = 1, \dots, K)

For 20% of the points, N, f_i, u_j \le 100, and K \le 10 for all i and j.

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

Input Specification

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

The second line contains distinct, space-separated positive integers u_1, \dots, u_K, the unlucky numbers.

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

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

Output Specification

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

Sample Input

4 13

Sample Output



  • 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.