Can anyone pls help me to solve this problem .... HAYBALE
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
8 | ecnerwala | 3494 |
9 | Um_nik | 3396 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | -is-this-fft- | 162 |
3 | maomao90 | 159 |
3 | atcoder_official | 159 |
5 | cry | 158 |
5 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | Dominater069 | 152 |
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;`