Hundreds of years ago, the once-opulent city of not-Atlantis incurred the wrath of the gods and was cast to the bottom of the ocean. Now, our intrepid adventurers have been sent to the lost city of not-Atlantis to retrieve forgotten lore recorded by the not-Atlanteans (along with whatever other treasure they can snag).
My question is: What sort of written media would survive at the bottom of the ocean for a few hundred years?
On one end of the spectrum, exposed paper would degrade and water-soluble pigments would run, which is unfortunate because I imagine these would be very common. On the other end of the spectrum, engraved stone would likely survive, but stone is a rather inconvenient method of recording information unless you deliberately need it to stand the test of time.
But there's a lot in between these two extremes. The ancient Greeks are well-known for painting things on pottery. Would such paintings survive underwater? Are there natural pigments, paints, or inks which would survive underwater? Are there paper-like materials which are waterproof and good for writing?
The conditions of storage might also change things. Could burying a book in mud at the bottom of the ocean (but not too deep that you can't find it) protect it from decay? It is possible that some of the more valuable tomes were cached in waterproof cases, but what sort of container would keep its contents dry while underwater for hundreds of years?
How could this forgotten lore have been recorded and/or stored to survive underwater for hundreds of years until our adventurers discover it?
Not-Atlantis had a technology level no more advanced than approximately medieval (I could do elements of Renaissance in a pinch, but there is definitely no plastic or digital media). Magic is abundant in this world, but we shall assume non-magical means of writing and preservation for the purposes of this question. The ruins of not-Atlantis need to be mostly navigable, not entirely buried in mud and silt. The water should be suitable for aquatic life. The not-Atlanteans were human-like sea-faring surface-dwellers before the cataclysm, so their common writings would not have deliberately needed to be waterproof (although they may have taken special steps to preserve a small number of choice texts).
The less contrived the circumstances for writing to survive under these conditions, the better. I suspect that real-world underwater archaeology and shipwreck salvaging could inform a good answer to this question.
There are several related questions on what sort of writing an underwater civilisation would use. This question differs in that we assume methods of writing developed by and readable by surface-dwelling people, and that I am interested in the longevity of such records (although I expect some overlap in the answers).