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

Added by:Sandeep Kumar Singh
Date:2017-08-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2020-09-16 08:24:09
fastio+set+'\n' => gives AC
2020-09-13 10:05:16 Rafail Loizou
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);"

Can anyone tell me why is this? Is there a chance that scanf/printf is faster even when compare with fast I/O cin/cout ?

[AFTER SEARCHING]: Turns out there are cases like this problem where just using the two commands to make cin/cout faster is not enough to pass the problem. You can avoid using scanf/printf in these cases by using the ultimate fastest I/O there is which is getchar_unlocked() and putchar_unclocked().

https://www.geeksforgeeks.org/getchar_unlocked-faster-input-cc-competitive-programming/

[NG]: Aside of very few problems with miscalculated TL, I/O method does not decide between AC and TLE in C. Again, if algo with good "complexity" doesn't pass using regular I/O methods, there are other issues in the code, mostly bad habits that will keep affecting your every solution if your ambition ends at getting the green bar even if the top time is 1/10 of yours. Problems with huge input are great opportunity to work on this, good luck. BTW. as others had pointed out, scanf/printf is enough for AC here. Use INTEST for I/O speed experiments.

Last edit: 2020-09-14 03:09:05
2020-05-22 13:47:09
Alas, test cases are weak. O(nq/32) is possible.
2020-05-12 15:41:23
Dang. How can i get SIGXFSZ verdict? Could someone kindly to explain why this happened?
2019-07-18 12:25:37
(Comment of anirudnits) +1
2018-06-09 12:27:40
lower_bound(s.begin(),s.end(),y) -> TLE
s.lower_bound(y) -> AC and use scanf and printf, cin cout even with fast i/o gave me TLE

Last edit: 2018-06-09 12:32:12
2017-09-28 21:58:15
for those using set..lowerbound has log^2 complexity...so it might not work
2017-08-09 12:35:28
answer is 2
but i am getting tle
2017-08-08 17:46:15 Vipul Srivastava
I am using scanf
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.