A10 - Resort Hotel

atcoder.jp

左からと右からの累積MAX(？)を計算しておく。

var N = int.Parse(Console.ReadLine()!);
var A = Console.ReadLine()!.Split(' ').Select(x => int.Parse(x)).ToList();
var D = int.Parse(Console.ReadLine()!);
var Q = new List<(int Left, int Right)>();
for (var i = 0; i < D; i++)
{
    var input = Console.ReadLine()!.Split(' ').Select(x => int.Parse(x)).ToList();
    Q.Add((input[0], input[1]));

}

// 左からの累積 MAX を計算
var L = new int[N];
L[0] = A[0];
for (var i = 1; i < N; i++)
{
    L[i] = Math.Max(L[i - 1], A[i]);
}

// 右からの累積 MAX を計算
var R = new int[N];
R[N - 1] = A[N - 1];
for (var i = N - 2; i >= 0; i--)
{
    R[i] = Math.Max(R[i + 1], A[i]);
}

for (var i = 0; i < D; i++)
{
    var left = Q[i].Left <= 1 ? 0 : L[Q[i].Left - 1 - 1];
    var right = Q[i].Right >= N ? 0 : R[Q[i].Right - 1 + 1];
    var answer = Math.Max(left, right);
    Console.WriteLine(answer);
}