TLE '17 Contest 2 P2 - Unlucky Numbers

View as PDF

Submit solution



Points:5 (partial)
Time limit:3.0s
Python10.0s
Memory limit:256M
Python256M
Author:

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.

Constraints

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

2
4 13
2
16
14

Sample Output

14
12

Report an issue

Comments


  • 1
    Tearful
     commented on Nov. 1, 2017

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


    • 0
      unsuspiciouscrumpet
       commented on Nov. 1, 2017

      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

        Fellow OTTAWA FRIEND!