Hello everyone! Can someone help me to figure out if my solution is incorrect? otherwise, help me what is wrong with my code?
I know there is an expected solution, but I wanna discard mine first.
This is the problem: http://www.spoj.com/problems/KQUERY/
This is my code in C++: http://ideone.com/22FvI4 //ignore all comments in Spanish xD
First, sorry if my english is bad.
Second, I'm indexing from 0.
So, my solution is:
sL and sR are vector where t is a class with atributes s, k and id. s is either a L (if it is in sL) or a R (if it is in sR) of a query; k is the K of a query and id is the index of a query.
To make it easier, sometimes I would say L or R instead of s to refer to the first atribute of a query in sL or sR.
I read the sequence and store it in vector v.
I read the queries. Let L, R and K be a query. I store {L-1, K, i} in a vector sL and {R, K, i} in a vector sR, where i is the index of the query.
//I subtract 1 to L because after I'd count number of elements greater than k before index L
Then I sort sL according to L and sR according to R.
I declare a vector Q of size q, initialized in {0,....,0} where at the end of the program, Q[i] = answer to i-th query.
Then I iterate over v.
Every time I encounter a L (remeber I subtracted 1 to all the Ls), I subtract number of elements greater than K to the corresponding box in Q[].
Every time I encounter a R, I add number of elements greater than K to the corresponding box in Q[]].
i.e
Let i,id and jd be variables that are going to be used to iterate over v, sL and sR, respectively.
As I said, I iterate over v.
I update BIT doing BIT_upd(v[i], 1).
While sL[id].s == i, I subtract (using BIT) the number of elements greater than sL[id].k to Q[sL[id].id] and add 1 to id.
While sR[jd].s == i, I add (using BIT) the number of elements greater than sR[jd].k to Q[sR[jd].id] and add 1 to jd.
I think this solution is O((n+q)*(logn + logq))
Then I print in order the results stored in Q[].