I just bought a laptop, a used one but still new enough to have UEFI and Windows 8. I resized windows C partition to make space for linux and created linux partitions (using gparted on a livecd). I rebooted normally into windows, I left the laptop on for a while, then I get back and I can't do anything. Black screen, HP logo in the middle and it says in a regular interval: 'analysing system', 'preparing automatic repair', 'Repairing HDD issues. It can take over an hour'. But why does it repeat this information? Obviously something is wrong.
I'm able to boot the livecd, but Windows won't boot. If I wiped the hdd and installed new system, would this screen appear again or it will boot os/bootloader fine?

Edit: I booted the livecd once more and C partition is now broken. It was perfectly fine, HP recovery destroyed it instead of repairing. There's probably no other way, but to wipe everything. But is it safe? Can I just erase HDD, install linux first and then windows?
http://postimg.org/image/v5wv6ddzf/

Posting from my motorcycle tuner laptop that is a Linux dualbooter.

My way was to first make recovery dvds of the Windows 7 drive on here so to bring it back to stock in case I re-sell it.
I shrinked Windows in Windows first and made left over space as unallocated. Then made it extended in gparted using live cd later.
After shrinking Windows using Windows Disk Manager. I rebooted to let Windows chkdisk run. After all the dust settled and I had a working Windows bootable laptop again. Just a smaller partition on the drive now holding Windows. I did my Linux install.

It's been setup this way for years now. I run the Windows for DRM Tuning software and Itunes ( I own a Iphone also).
Everything else is done in linux on this laptop.

Your screen shot covers up what sda1 and sda2 are. Looks to me you should be able to bail yourself out of this mess with
a Windows recovery reinstall using one of the key combos on your laptop for that purpose. Google search will tell you what that is. (mine is the F4 key)
So that is where I would start 1st. Bring the laptop back to virgin state.

Start over. As far as Windows Linux install order. My practice is to let Windows be installed first. Then follow up with a Linux install. Just easier for me to handle.

So I guess what I am saying.
1. Do a recovery reinstall. sda1 or sda2 is where that reinstall image is sitting I bet. But cannot be sure because of your screenshot covers them up and no info posted on what they are. There are probably hot keys to do this after a power on.
2. After recovery reinstall and everything settles down. Make recovery media using the tools provided in Windows and your laptop. Pack them up and put them away for later needs.
3. Shrink Windows using Windows Disk Manager.
4. Reboot numerous times to make sure everything is fine after that.
5. Install the linux of your choice then.

Heck. Just realized my post may be for nothing. Not sure but maybe sda4 is where the recovery image was and is now broken. So never mind.

It could be a hardware problem. Determine the manufacturer of the hard drive using the livecd, eg Western Digital, Seagate, etc. Go to the manufacturer's website and download their diagnostic utilities iso. The major manufacturers have their diagnostic utilities in bootable iso form on their websites. Burn the iso as an image like you would a linux distro installation cd and use it to boot into the diagnostic utilities. Run the diagnostics in thorough mode and see if there are any problems.

If no problems are found and assuming you have a windows installation dvd, I would delete all the partitions with gparted and install windows first. Then shrink your main windows partition with gparted and install linux on the resulting unallocated space.

Thanks for sharing your experience. I've just looked at replies. I have already restored system to factory state. Windows works. I have obtained my Windows key and prepared Windows 8 image and burned it in case something goes wrong again. Now I'm updating Windows and then I will update it to 8.1 and prepare 8.1 image. Then like you said I will shrink Windows in Windows. There's one little difference however, you probably don't have UEFI as you mentioned extended partitions and this UEFI is something I don't understand completely. Well after I burn Windows 8.1 and shrink C partition, I will try to install Arch linux. Hope it all goes well.
I learned to install Windows first the hard way. One time I was installing Windows 7, apart from updating MBR to its loader, it also deleted bootable linux partition, which contained my OS. I had to waste time on reinstalling, good thing it didn't delete my home partition. Playing with partitions using Gparted is much safer for data than installing Windows.
I will post an update once I deal with everything or encounter any problems.