SPOJ.com - Problem SOLVEIT

SOLVEIT - SOLVEIT

no tags

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

Submit solution!

hide comments

< Previous 1 2 Next >

	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);" 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
	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 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
	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 but i am getting tle
	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

Submit solution!

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