red_coder's blog

SPOJ problem stuck!!!
By red_coder, 14 years ago, In English

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

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
14 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

anyone please help...

→ Reply
»
14 years ago, hide # |
← Rev. 4  
Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
14 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
14 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
14 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

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;`

→ Reply