Given falling acid drops in columns, decide whether the single-pixel disc can stay at some height and cross without ever touching a drop.
Medium6Dynamic programmingSliding windowPrefix sumMathNo attempts yetTime limit2sMemory limit512 MBYou are playing a computer game in which you throw discs horizontally from the left side of the screen to the right. Acid keeps dripping straight down from several points in the ceiling to the ground, and any contact with the acid destroys your disc at once. After failing a few times, you want to know whether reaching the other side is possible at all.

There are n dripping spots on row 0. A drop that starts at dripping spot k falls v pixels every time your disc moves one pixel to the right. When a drop reaches the ground, a new drop starts falling from the dripping spot in the same column, so each of those columns holds exactly one acid drop at every moment. At time t, the drop in the column of dripping spot k sits at vertical position
(yk+t⋅v)modh,
where yk is the vertical position of the k-th drop at time 0 and h is the height of the ceiling.
Your disc and the acid drops move in alternation. First your disc moves one pixel to the right, then every acid drop moves v pixels downwards, visiting each pixel on the way. Your disc is a single pixel thick and w pixels wide, and an acid drop occupies a single pixel. The disc is destroyed if it ever occupies the same pixel as an acid drop. You can throw at any height between 0 and h−1 inclusive, and the disc keeps that height for the whole journey. At time 0 the disc occupies columns −w through −1 inclusive. The journey is complete once the left side of the disc reaches column 200000.
The first line contains four integers n, h, v and w, where n (1≤n≤200000) is the number of dripping spots, h (1≤h≤200000) is the ceiling height, v (1≤v≤500) is the dripping speed and w (1≤w≤500) is the width of the disc.
Each of the next n lines describes one acid drop with two integers x (0≤x<200000), the column of the drop, and y (0≤y<h), its vertical position at time 0.
No two acid drops have the same x.
Print VICTORY if some throwing height carries the disc through the acid without being destroyed. Otherwise print GAME OVER.