Can anyone pls help me to solve this problem .... HAYBALE
# | User | Rating |
---|---|---|
1 | tourist | 3843 |
2 | jiangly | 3705 |
3 | Benq | 3628 |
4 | orzdevinwang | 3571 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | jqdai0815 | 3530 |
8 | ecnerwala | 3499 |
9 | gyh20 | 3447 |
10 | Rebelz | 3409 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 163 |
3 | adamant | 162 |
4 | TheScrasse | 158 |
5 | nor | 153 |
5 | maroonrk | 153 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
9 | orz | 145 |
10 | pajenegod | 144 |
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;`