I wouldn't bother with bistable relays just to hold a logic state - too big, expensive and difficult to drive.
Instead, I'd use a CMOS 8 bit transparent latch with a backup battery and a PSU supervisor IC + a bit of glue logic, to latch the contents when the power goes away. e.g.if you choose
74HC573 which will hold its state down to 2.0V and a leading brand CR2032 coin cell as the backup battery, you can expect over 30 months of power-off data retention per battery.
There are a few devils in the details: you need a pair of low leakage Schottky diodes to route both battery power and +5V to the latch so the battery takes over when the 5V goes away, cathodes to the latch Vcc pin, anodes to each power source. e.g the common cathode
BAS70-05 low leakage double Scottky diode, which typically leaks less than a uA at 5V reverse voltage and 85 deg C.
The74HC573 needs a pullup on its /OE pin to its own Vcc pin to turn its outputs and something to pull that pin low when the 5V rail is up. e.g a
SN74LVC1G06 single gate open drain Schmitt inverter, powered from the 5V rail with its input fed from a potential divider with 80% of the 5V rail so it doesn't pull the /OE pin low till the 5V rail is well above the battery voltage and a circuit to take LE low and latch the current data as soon as the 5V starts to dip, but only let it go back high after the reset pulse is finished, so the data on its outputs from the previous session is latched into the counters parallel data inputs when their pre-load pins go high. Basically whatever drives LE must be quick to go low and slow to go high, or even delayed off the reset pulse.
HTH,
Ian.