The LM78XX series is rated to a maximum input voltage of 35V, so yes, your 36V battery pack is too high. On top of that, all of that voltage drop from 36V to 12V or 5V will be burned off as heat, so the power dissipation could also be a concern depending on how much current the circuits will draw.
Would there be any way to configure the battery pack for a lower voltage, such as 18V? 15V might also work depending on how much the voltage of the pack drops over its discharge range. If the voltage drops any lower than 14V, you may run into issues with the dropout voltage of the 7812.
Edit:
okay, so for 500mA @ 12V, that would be a voltage drop of 24V, which would be 12W of heat dissipated at the regulator. This would probably overheat unless you had reasonably good heatsinking on the 7812. For an 18V pack, the dissipation @500mA drops to 3W.