Can anyone pls help me to solve this problem .... HAYBALE
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
Can anyone pls help me to solve this problem .... HAYBALE
Название |
---|
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;`