All Tracks Data Structures Advanced Data Structures Segment Trees Problem

HELP MONA!!!
Tag(s):

Medium

Problem
Editorial
Analytics

Little peter is a student of The Castle School and he recently learned about odd numbers.His friend Joy loves programming but he is very weak in odd numbers.Today Peter wants to play cricket with Joy but it is raining outside .So,Peter got bored and he gave Joy a question to solve.

Peter gave Joy N numbers represented by an array A of size N and Q queries.Each query can be of two types-

1. 1 i -In this type of query add 1 to the i th element of Array A
2. 2 K - In this type of query print the index of the Kth odd number in the Array A,if exists ,else print -1

Where, 
       1<=N<=2*10^6
        1<=Q<=2*10^6
        1<=K<=2*10^6
        1<=i<=2*10^6

Assume all 1 based Indexing are there

 

As the constraints are much higher Joy asks help to his girlfriend Mona.As Mona is new to programming help her to solve the problem.

INPUT: First line of inputs contain two space separated integers N and Q representing number of elements in the Array A and number of queries respectively.
Next line consists of N space separated integers denoting the value of the elements of the array initially.
Next Q lines contain query of two types as described above.
OUTPUT: Output the index of the Kth odd number of the Array A in a new line in each of the second type of query

 

 

SAMPLE INPUT
6 7
2 3 4 1 3 6
2 3
1 3
1 6
2 4
1 4
2 6
2 2
SAMPLE OUTPUT
5
5
-1
3
Time Limit: 6,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Codeclub jusl

Challenge Name

ALGOMANIAC PRELIMS

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?