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 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;
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;
Print a single line for each query type 2 containing index which has value -1 and is greater or equal to input index y
Input: 5 5
2 2 Output: -1
fastio+set+'\n' => gives AC
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);"
Alas, test cases are weak. O(nq/32) is possible.
Dang. How can i get SIGXFSZ verdict? Could someone kindly to explain why this happened?
(Comment of anirudnits) +1
lower_bound(s.begin(),s.end(),y) -> TLE
for those using set..lowerbound has log^2 complexity...so it might not work
answer is 2
I am using scanf
I used stl set too... if u use cin , cout , use fast i/oLast edit: 2017-08-08 16:49:22