Sachverhalt: A. Am 27. September 2009 beschloss das St. Moritzer Stimmvolk eine Teilrevision der von 1999/2000 stammenden Ortsplanung in Form einer projektbezogenen Nutzungsplanung für das Gebiet des Hotels Suvretta House, bestehend aus Zonenplan, Generellem Gestaltungsplan (GGP) und Generellem Erschliessungsplan (GEP) "Suvretta House", den Vorschriften zum GGP und GEP sowie den Baugesetzvorschriften. Ziel dieser Teilrevision ist es, die nutzungsplanerische Basis für die Weiterentwicklung und die langfristige Existenzsicherung des hundertjährigen Fünf-Sterne-Hotels Suvretta House zu schaffen. Der GGP stützt sich auf das Nutzungs-, Erschliessungs- und Gestaltungskonzept des "Masterplan Vision Suvretta 2025 St. Moritz" vom 2. April 2008 (im Folgenden: Masterplan). Dieser sieht im Wesentlichen folgende Um- und Neubauten vor: - Einbau zusätzlicher Hotelzimmer im Haupthaus mittels Aufstockung des Seitenflügels und Ergänzung des Hauptgebäudes mit talseitig angeordneter Sockelbaute für Restaurant und Wellness in den Baustandorten A1-A4; - ein neues Sporthotel im Baustandort B; - ein Suitenhotel der 6-Sterne-Kategorie in den Baustandorten D1-D4; - ein Sportcenter für die Integration verschiedener Nutzungen im Zusammenhang mit Winter- und Sommersport im Baustandort C. Der Planungsperimeter umfasst 46'473 m2 Land am Suvretta-Hang zwischen der Via Suvretta und der Via Somplaz. Das Gebiet liegt grösstenteils (zu 41'951 m2) in der Villenzone. Dort sind Wohnbauten mit nicht mehr als 2 Herdstellen bei einer Ausnutzungsziffer (AZ) von 0.2, einer maximalen Gebäudehöhe von 10 m sowie einem kleinen Grenzabstand von 6 m und einem grossen Grenzabstand von 10 m zugelassen. Der Planungsperimeter wurde in die Hotelzone Suvretta House umgezont. Diese ist in Art. 80a Baugesetz St. Moritz (BG) wie folgt geregelt: "Art. 80a Hotelzone Suvretta House 1. Die Hotelzone Suvretta House ist bestimmt für gastgewerbliche Betriebe und die dazugehörigen Bauten und Anlagen wie Personalunterkünfte, Sport- und Freizeitanlagen, Parkierungsanlagen und dergleichen. 2. In der Hotelzone Suvretta House sind auch Dienstleistungs- und Gewerbebetriebe zulässig. Solche die Hauptnutzung ergänzende Nutzungen dürfen maximal 30% der auf den Grundstücken insgesamt realisierten anrechenbaren Bruttogeschossflächen beanspruchen." 3. [Verweis auf GGP, GEP und die zugehörigen Vorschriften]. 4. [Bauvorhaben an bestehenden inventarisierten Objekten]. Der GGP legt verschiedene Baubereiche fest (A1-A4, B, C, D1-D4) und sieht als Richtwerte folgende Bruttogeschossflächen (BGF) vor: - Baustandort A (Hotelstandort) 27'000 m2 - Baustandort B (heute unüberbaut) 8'200 m2 - Baustandort C (heute grösstenteils überbaut) 2'000 m2 - Baubereiche D1 (heute unüberbaut) 800 m2 - Baubereich D2 (heute weitgehend unüberbaut) 2'400 m2 - Baubereich D3 (heute unüberbaut) 2'600 m2 - Baubereich D4 (heute unüberbaut) 2'000 m2. Durch Nutzungsverlegungen darf die Nutzung beim empfangenden Baubereich nicht um mehr als 20% erhöht werden. Gesamthaft (in allen Baubereichen) stehen gemäss neuem Zonenplan max. 45'000 m2 BGF zur Verfügung, statt bisher 8'390 m2 (nach geltendem Zonenplan) bzw. 25'165 m2 (effektiv vorhandene BGF mit Bestandesgarantie). An den Baustandorten A, B und C ist die Gebäudehöhe mittels Höhenkote festgelegt; in den Bereichen D1-D4 gilt gemäss GGP eine maximale Gebäudehöhe von 10 m und eine maximale Gebäudelänge von 30 m (D1) bzw. 20 m (D2-4). Teilweise sind der Waldabstand und der Gewässerabstand reduziert. Das Flachdachverbot gemäss Art. 27 Abs. 5 BG ist aufgehoben. Für die Projektrealisierung ist eine temporäre Rodung von 239 m2 und eine permanente Rodung von 1'060 m2 erforderlich. Die gerodete Fläche wird in unmittelbarer Nähe aufgeforstet. Zur Schaffung der Baubereiche D2 und D3 ist vorgesehen, den bestehenden Bach, der z.T. oberirdisch verläuft und z.T. eingedolt bzw. kanalisiert ist, in nordöstliche bzw. östliche Richtung zu verlegen; er soll neu auf der gesamten Strecke oberirdisch geführt werden. B. Am 2. November 2009 erhoben u.a. X._ (Eigentümer der Parzelle Nr. 2181), Y._ (Eigentümer der Parzelle Nr. 2237) und die Erbengemeinschaft V._ (Eigentümerin der Parzelle Nr. 1861) gemeinsam Planungsbeschwerde bei der Regierung des Kantons Graubünden. Diese wies die Beschwerde sowie die Rodungseinsprache am 12. April 2011 ab. Gleichentags genehmigte sie die angefochtene Nutzungsplanung und erteilte die Genehmigung zur Rodung von 1'298 m2 Waldareal unter Auflagen und Bedingungen. Die wichtigsten Auflagen sind: - Für die Bachverlegung im oberen Teil werden die Bewilligungen zur Entfernung von Ufervegetation gemäss Art. 22 Abs. 2 des Bundesgesetzes vom 1. Juli 1966 über den Natur- und Heimatschutz (NHG; SR 451), zur Gewässerkorrektur nach Art. 37 des Bundesgesetzes vom 24. Januar 1991 über den Schutz der Gewässer (GSchG; SR 814.20) und für neue Eindolungen für Verkehrsübergänge nach Art. 38 GSchG in Aussicht gestellt. Die kommunale Baubehörde müsse das Projekt für die Bachverlegung vor Erteilung der Baubewilligung dem Departement für Erziehung, Kultur und Umwelt (EKUD) unterbreiten, welches prüfe, ob die Gestaltung des verlegten Bachs den Anforderungen von Art. 37 Abs. 2 GSchG entspreche und ob die Anforderungen der Wasserbaugesetzgebung erfüllt seien (Abschnitt I Auflage 4a). - Sofern Gebäude am Baustandort D2 nicht so platziert werden könnten, dass sie einen Abstand von 10 m zum verlegten Bach einhalten, könne die kommunale Baubehörde gemäss Art. 78 Abs. 2 des Raumplanungsgesetzes für den Kanton Graubünden vom 6. Dezember 2004 (KRG) in der Baubewilligung eine Ausnahme gewähren, wobei sie vorgängig das kantonale Amt für Natur und Umwelt (ANU) anzuhören habe (Abschnitt I Auflage 4c). - Das Baugesuch habe aufzuzeigen, welche schützenswerten Lebensräume mit den Bauvorhaben beeinträchtigt oder zerstört werden und müsse nach Absprache mit dem ANU einen Vorschlag für angemessene Schutz- und Ersatzmassnahmen enthalten. Die kommunale Baubehörde lege auf Antrag des ANU die Wiederherstellungs- und Ersatzmassnahmen in der Baubewilligung fest (Abschnitt I Auflage 4d). - Vom Projekt sei voraussichtlich einer der beiden Standorte des gefleckten Knabenkrauts auf oder bei Trockenwiesen und -weiden (TWW-Objekte) betroffen (im Baufeld D4) sowie eventuell ein Standort des gefleckten Knabenkrauts oder des Türkenbunds im Bereich der Rodungsfläche für das Baufeld B. Dafür bedürfe es einer Ausnahmebewilligung für die Entfernung der Pflanzen. Diese werde in Aussicht gestellt. Die Baubehörde müsse ein entsprechendes Gesuch im Rahmen des Baubewilligungsverfahrens dem EKUD weiterleiten (Abschnitt I Ziff. 4e). - Als Ersatz für die permanente Rodung von 1059 m2 sei eine flächengleiche Ersatzleistung bis Ende 2020 im Benehmen mit dem Regionalforstingenieur vorzunehmen (Abschnitt II Auflage 1d). C. Gegen die regierungsrätlichen Entscheide erhoben X._, Y._ und Z._ (welche die Parzelle Nr. 1861 von der Erbengemeinschaft V._ übernommen hat) am 30. Mai 2011 gemeinsam Beschwerde an das Verwaltungsgericht des Kantons Graubünden. Dieses führte am 16. Dezember 2011 einen Augenschein durch. Am 24. Januar 2012 wies es die Beschwerde ab. D. Gegen den verwaltungsgerichtlichen Entscheid haben X._, Y._ und Z._ am 21. März 2012 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen, der Beschluss der Urnengemeinde St. Moritz vom 27. September 2009 respektive die Teilrevision Ortsplanung St. Moritz, Gebiet "Suvretta House" samt den Beschlüssen der Regierung des Kantons Graubünden betr. Genehmigung Nutzungsplanung mit integrierter Rodungsbewilligung (Protokoll Nr. 290) und betr. Beschwerdeentscheid (Protokoll Nr. 292), beide vom 12. April 2011, seien aufzuheben und es sei das Gebiet "Suvretta House" gemäss bisheriger Zonenplanung in der Villenzone zu belassen. Eventuell sei die Sache zur Überarbeitung an die Gemeinde St. Moritz zurückzuweisen. Subeventuell seien die angefochtenen Beschlüsse dahingehend aufzuheben, dass die folgenden Änderungen in den Ortsplanungsgrundlagen vorgenommen würden: Zonenplan: a) Der Baustandort D4 sei in der Villenzone zu belassen. b) Der Baustandort D2 sei in der Villenzone zu belassen, eventuell im südlichen Bereich zu reduzieren. c) Der Baustandort B sei in der Villenzone zu belassen, eventuell in die Hotelzone umzuteilen unter Erlass verschiedener Beschränkungen im GGP gemäss nachfolgenden Anträgen. Genereller Gestaltungsplan (GGP): a) Die Spezialbestimmungen zum Baustandort D4 seien zu streichen. b) Folgende Bruttogeschossflächen seien zu reduzieren: - Baustandorte D1 und D2 (für beide): auf 2'000 m2 - Baustandort D3: auf 1'200 m2 - Baustandort B: auf 4'000 m2. c) Auf die Bachverlegung sei zu verzichten. d) Die Gebäudehöhe am Baustandort B sei auf 1'900 m.ü.M. zu begrenzen. e) Auf die Rodung am Baustandort B sei zu verzichten. Genereller Erschliessungsplan (GEP): Auf die unterirdische Tiefgarage westlich des Hotels Suvretta House (unter D1 und D2) sei zu verzichten, eventuell sei mindestens die Zufahrt der Tiefgarage über die Via Chasellas fallen zu lassen. Vorschriften zum GGP und GEP: a) Art. 3 sei insbesondere hinsichtlich Situierung und Ausmass der Baukuben präziser und verbindlicher zu formulieren. b) Zu Art. 8: Durch Nutzungstransporte dürfe die Aussennutzung an einem Baustandort um maximal 10% (nicht 20%) erhöht werden. Nutzungsverlegungen in die Baustandorte D3, D1 und D2 sowie B seien auszuschliessen. c) Art. 6 "Weitere Bereiche" sei vollständig zu streichen. d) In Art. 9 sei die ganze Bestimmung zu streichen, wonach "geringfügige Abweichungen bis 0.5 m" in gewissen Baustandorten zulässig seien. e) Hinsichtlich Kostenregelung (Art. 14) sei eine Spezialregelung vorzusehen, welche ausschliesslich oder zumindest vorwiegend die initiierende und profitierende Grundeigentümerin der Planrevision für kostenpflichtig erklärt. Nachweis und Garantien: Es seien Garantien in den Bestimmungen aufzunehmen, welche Finanzierungsnachweise und entsprechende Garantien für eine Realisierung vorsehen sowie eine spätere Zweckentfremdung von Anlagen der traditionellen Hotellerie verhindern. Eventuell sei die Sache zu neuem Entscheid an das Verwaltungsgericht, subeventuell an die Regierung, zurückzuweisen. E. Die AG W._ (im Folgenden: die Beschwerdegegnerin), die Gemeinde St. Moritz und das Verwaltungsgericht beantragen, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Das Departement für Volkswirtschaft und Soziales Graubünden schliesst namens der Bündner Regierung auf Abweisung der Beschwerde. Das Bundesamt für Umwelt (BAFU) kommt in seiner Vernehmlassung zum Ergebnis, dass der angefochtene Entscheid mit dem Bundesrecht in den Bereichen Gewässerschutz, Arten- und Lebensraumschutz sowie Wald vereinbar sei. F. Den Parteien wurde Gelegenheit gegeben, sich zu den Vernehmlassungen, insbesondere des BAFU, zu äussern. In ihrer Replik ergänzen die Beschwerdeführer ihren Antrag dahin, dass auch die Aufhebung des verwaltungsgerichtlichen Entscheids verlangt werde. G. Mit Verfügung vom 7. Mai 2012 wurde der Beschwerde aufschiebende Wirkung beigelegt, soweit ihr diese Wirkung nicht bereits von Gesetzes wegen zukommt. 