Can anyone pls help me to solve this problem .... HAYBALE
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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;`