Link to the Problem

Problem

Alice and Bob are playing with palindrome.

First, Bob writes \(N\) natural numbers on a board. Then he asks Alice a total of \(M\) questions.

Each question is represented by two integers \(S\) and \(E\)(\(1 \le S \le E \le N\)). The question asks whether the sequence of numbers from the \(S\)-th number to the \(E\)-th number forms a palindrome. Alice must answer either "palindrome" or "not palindrome" for each question.

For example, suppose the numbers written on the board are: \(1\), \(2\), \(1\), \(3\), \(1\), \(2\), \(1\).

• If \(S = 1\), \(E = 3\), the sequence \(1\), \(2\), \(1\) is a palindrome.
• If \(S = 2\), \(E = 5\), the sequence \(2\), \(1\), \(3\), \(1\) is not a palindrome.
• If \(S = 3\), \(E = 3\), the sequence \(1\) is a palindrome.
• If \(S = 5\), \(E = 7\), the sequence \(1\), \(2\), \(1\) is a palindrome.

Given \(N\) natural numbers and \(M\) questions, write a program that determines Alice's answer for each question.

Input

The first line contains the length of the sequence, \(N\) (\(1 \le N \le 2\,000\))

The second line contains \(N\) natural numbers written on the board in order. Each number is less than or equal to \(100\,000\).

The third line contains the number of questions, \(M\) (\(1 \le M \le 1\,000\,000\)).

The next \(M\) lines each contain two integers \(S\) and \(E\), representing a question.

Output

For each of the \(M\) questions, output \(1\) if the sequence from the \(S\)-th number to the \(E\)-th number is a palindrome, and \(0\) otherwise, in the same order as the questions, one per line.

If the \(S\)-th element and the \(E\)-th element of the sequence are equal and the sequence starting from \(S+1\) to \(E-1\) is a palindrome, then the sequence from \(S\) to \(E\) is a palindrome as well. Therefore, it is easily solvable with two-dimensional DP.

Pay attention to the exception that occurs when \(S = E-1\).

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
int arr[2005];
bool dp[2005][2005];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    for(int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
    
    for(int i = N; i >= 1; i--) {
        dp[i][i] = true;
        dp[i][i+1] = (arr[i] == arr[i+1]);
        
        for(int j = i+2; j <= N; j++) {
            if(arr[i] != arr[j]) continue;
            
            dp[i][j] = dp[i+1][j-1];
        }
    }
    
    cin >> M;
    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        
        cout << dp[a][b] << "\n";
    }
    return 0;
}