Don't know much about video encoding, but I imagine there are some clever tricks google can pull to embed the ads with keyframes, since when you upload your video to youtube they already do re-encodes. I'm imagining there's some hand wavey stuff that would allow you to sorta concat the ad with different parts of the video.

I'd also imagine that the newer video codecs were explicitly designed to make stuff like this possible without a ton of computational resources.