TLE '17 Contest 2 P2 - Unlucky Numbers

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 3.0s
Python 10.0s
Memory limit: 256M
Python 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^{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 \leq N \leq 1\,000\,000
1 \leq K \leq 500\,000
1 \leq f_i \leq 1\,000\,000\ (i = 1, \dots, N)
1 \leq u_j \leq 1\,000\,000\ (j = 1, \dots, K)

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

For an additional 30% of the points, N, f_i, u_j \leq 100\,000, and K \leq 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^{th} line contains f_i, the top floor number of the i^{th} apartment. It is guaranteed that no top floor number is an unlucky number.

Output Specification

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

Sample Input

4 13

Sample Output



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

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

    • 0
      unsuspiciouscrumpet  commented on Nov. 1, 2017, 8:11 p.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.

      • 0
        Tearful  commented on Nov. 11, 2017, 9:07 p.m.

        Fellow OTTAWA FRIEND!