Can anyone pls help me to solve this problem .... HAYBALE
# | User | Rating |
---|---|---|
1 | ecnerwala | 3649 |
2 | Benq | 3581 |
3 | orzdevinwang | 3570 |
4 | Geothermal | 3569 |
4 | cnnfls_csy | 3569 |
6 | tourist | 3565 |
7 | maroonrk | 3531 |
8 | Radewoosh | 3521 |
9 | Um_nik | 3482 |
10 | jiangly | 3468 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 162 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 151 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Can anyone pls help me to solve this problem .... HAYBALE
Name |
---|
anyone please help...
We have a new array q[N], for each FJ instructions l..r doing q[l]++, q[r + 1]--. After all instructions for integer cnt = 0 from 1..N we will increase cnt += q[i] and h[i] = cnt, then sort(h, h + N) and print h[(N + 1) / 2].
dude i am not able to understand the logic behind your solution...
Another solution is to use segment tree and make an update on [A..B] segment for each instruction.
but dude, segement trees are used to find the min/max element in a given range .... how we would use that for updating all the elements in the range..
http://wcipeg.com/wiki/Segment_tree#Variations
It's a usaco problem.Although the code is very small the solution behind this code is not very simple. http://usaco.org/current/data/sol_restack.html
dude can u pls post the link of the Question...
1) calculate resulting heights of each stack 2) sort them 3) output middle element
step 1 can be done using segment trees, RSQ — Range Sum Query, QSRT decomposition, etc.
the simplest way to count resulting heights:
to remember each query L, R in addition array
dh[L]++, dh[R + 1]--;
thencurH = 0; for(i = 0; i < n; i++) {curH += dh[i]; h[i] = curH;}
sort(h, h + n); cout << h[((n) +-1) / 2 +-1] << endl;`