AYJCC24 P4 - Simon's Moon Dilemma
Simon, on the run after laundering money from clubs, is now trapped on the moon. In front of him are \(N\) checkpoints, with the \(i\)th checkpoint at an elevation of \(h_i\).
Simon's form of transportation, however, is just an old moon buggy, and it has a special mechanism: Once it has been lowered in elevation, it cannot increase its elevation. That is to say, if Simon wishes to go from checkpoint \(l\) to checkpoint \(r\), the elevations of the checkpoints between \(l\) and \(r\) must first be non-decreasing, then non-increasing. This means that there must be an integer \(m (l \le m \le r)\) such that \(h_{l} \le h_{l+1} \le h_{l+2} \le ... \le h_{m} \ge h_{m+1} \ge h_{m+2} \ge ... \ge h_{r}\).
Simon sees pizza at some of the checkpoints and, being the person he is, has ordered you to figure out if it is possible to travel from checkpoint \(l\) to \(r\).
Constraints
\(1 \le l_{i} \le r_{i} \le N\)
\(1 \le h_{i} \le 10^{9}\)
Subtask 1 [30%]
\(1 \le N, Q \le 10^{3}\)
Subtask 2 [70%]
\(1 \le N, Q \le 10^{6}\)
Input Specification
The first line contains \(2\) integers, \(N\) and \(Q\), the number of checkpoints and the number of queries. The second line contains the integers \(h_{1}, h_{2}, ... , h_{N}\), where \(h_{i}\) is the elevation of the \(i\)th checkpoint.
The following \(Q\) lines are the queries. The \(i\)th line contains the \(i\)th query, which is made up of 2 integers \(l_{i}\) and \(r_{i}\), the starting and ending checkpoints that Simon wishes to travel.
Output Specification
Print \(Q\) lines, in the \(i\)th line print the sentence "GO SIMON GO" if Simon is able to travel from \(l_{i}\) to \(r_{i}\), or "Such a Silly Simon" if Simon is unable to reach the target checkpoint.
Sample Input
8 6
2 3 2 4 4 6 3 2
1 3
2 3
2 4
8 8
1 4
5 8Sample Output
GO SIMON GO
GO SIMON GO
Such a Silly Simon
GO SIMON GO
Such a Silly Simon
GO SIMON GO
Comments
Least fraud Jimmy moment
https://codeforces.com/contest/279/problem/C
timmy jao