Блог пользователя red_coder

Автор red_coder, 12 лет назад, По-английски

Can anyone pls help me to solve this problem .... HAYBALE

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

anyone please help...

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится +4 Проголосовать: не нравится

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].

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Another solution is to use segment tree and make an update on [A..B] segment for each instruction.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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]--; then curH = 0; for(i = 0; i < n; i++) {curH += dh[i]; h[i] = curH;} sort(h, h + n); cout << h[((n) +-1) / 2 +-1] << endl;`