SOLVEIT - SOLVEIT
Problem setter of INSOMNIA, MNNIT Allahabad decided to set a easy problem for all coders so that they can easily solve the problem and boost their confidence for rest of INSOMNIA.
The problem is a follows: You are given an array of size n which is initialized with 0. You will be given q queries of two types:
Type 1: set in (input value) index k to -1.
Type 2: print the index which has value -1 and is greater or equal to input index y. If there is no such value print -1.
Note: Indexing is 1 based.
Input
First line contains two integers n and q separated by spaces.
Next q lines contains type of query and for type 1 query integer k separated by a space and for type 2 integer y separated by a space.
1 <= n <= 10^6
1 <= q <= 10^6
1 <= y, k <= n
Output
Print a single line for each query type 2 containing index which has value -1 and is greater or equal to input index y.
Example
Input: 5 5 2 3 1 2 2 1 2 3 2 2 Output: -1 2 -1 2
hide comments
vineetjai:
2020-09-16 08:24:09
fastio+set+'\n' => gives AC |
|
Rafail Loizou:
2020-09-13 10:05:16
I made 2 implementations with different data structures. In one case the data structure was in stack memory and in the other it was in the heap memory. Both cases passed when I used scanf/printf and both failed when I used cin/cout with fast I/O " ios::sync_with_stdio(false); " and "cin.tie(0);"
|
|
feodorv:
2020-05-22 13:47:09
Alas, test cases are weak. O(nq/32) is possible. |
|
aditya_rev:
2020-05-12 15:41:23
Dang. How can i get SIGXFSZ verdict? Could someone kindly to explain why this happened? |
|
kshubham02:
2019-07-18 12:25:37
(Comment of anirudnits) +1 |
|
anirudnits:
2018-06-09 12:27:40
lower_bound(s.begin(),s.end(),y) -> TLE
|
|
starbot:
2017-09-28 21:58:15
for those using set..lowerbound has log^2 complexity...so it might not work |
|
mani_123:
2017-08-09 12:35:28
answer is 2
|
|
Vipul Srivastava:
2017-08-08 17:46:15
I am using scanf |
|
pvsmpraveen:
2017-08-08 16:48:32
I used stl set too... if u use cin , cout , use fast i/o Last edit: 2017-08-08 16:49:22 |
Added by: | Sandeep Kumar Singh |
Date: | 2017-08-04 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |