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 while 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;

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 while 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
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
Vipul Srivastava: 2017-08-08 15:58:11

I am using set for my solution and the complexity is Qlogn I am getting TLE, can someone suggest if its a problem using stl for the solution?

pvsmpraveen: 2017-08-08 15:45:14

QlogN is sufficient.

starbot: 2017-08-07 09:35:39

@vipul seems so

sas1905: 2017-08-05 13:32:22

For Type 2 print the smallest index(if exists) greater than equal to y which has the value of -1.

Vipul Srivastava: 2017-08-05 11:00:31

Is qlog(n) insufficient for this problem?


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