TLEOJ Contest #16 - Truy vấn MEX

View as PDF

Submit solution

Points: 1900
Time limit: 0.96s
Memory limit: 128M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C++, pypy3, Python

Hôm nay giaminh2211 được học định nghĩa của MEX của tập hợp và cảm thấy rất hứng thú với định nghĩa này nên đã nghĩ ra 1 bài toán liên quan đến hàm MEX này.

Cho mảng n phần tử a_1, a_2, …, a_n.
Cho q truy vấn, mỗi truy vấn bạn được cho 1 số nguyên dương x.
Xét mảng b với b_i=a_i+i \times x với (1 \leq i \leq n).
Với mỗi truy vấn hãy in ra MEX của mảng b của truy vấn đó.

Định nghĩa của MEX
Định nghĩa MEX của tập S

MEX của một tập hợp S là số nguyên không âm nhỏ nhất không thuộc tập hợp S .

Giải thích cụ thể
  • MEX của S là số nguyên không âm nhỏ nhất mà không xuất hiện trong S .
  • Ví dụ:
  • Nếu S = \{0, 1, 2, 4, 5, -3\} , thì MEX của S 3 3 là số nguyên không âm nhỏ nhất không có trong S .
  • Nếu S = \{1, 2, 3, -1, -2, -3, 69, -96, 169, 196, -11092001\} , thì MEX của S 0 0 là số nguyên không âm nhỏ nhất không có trong S .

Input and Output

Input
  • Dòng đầu chứa hai số nguyên n, q (1 \leq n, q \leq 10^5)
  • Dòng thứ hai chứa n số nguyên a_i (-10^9 \leq a_i \leq 10^9)
  • q dòng sau dòng thứ i gồm 1 số nguyên dương là x (1 \leq x \leq n) của truy vấn thứ i
Output
  • Một dòng duy nhất chứa số nguyên là đáp án của bài toán
Subtask
  • Subtask 1 (50\% số điểm) : 1 \leq n, q \leq 1000.
  • Subtask 2 (50\% số điểm còn lại) : Không có giới hạn gì thêm.

Test 1

Input
5 2
-1 -1 -6 -2 4
1
2
Output
3
2

Comments

There are no comments at the moment.