11046 팰린드롬??

11046 팰린드롬?? https://www.acmicpc.net/problem/11046

자연수 N개가 주어진다.
M개의 쿼리마다 $s$부터$e$구간 까지 팰린드롬을 이루는지 여부를 판단하는 문제이다.

Manacher's algorithm으로 전처리하여 각 쿼리마다 $O(1)$에 처리할 수 있다.
짝수의 팰린드롬도 처리하기 위해 시작,끝,중간마다 $-1$을 집어넣었다.

const int MAXN = 1e6 + 6; int arr[MAXN * 2 + 6];

cs

이 문제를 20번 넘게 정도 제출했는데 위와 같이 const 변수에 곱셈을 적용시키면 안된다ㅠㅠ

#include <bits/stdc++.h> using namespace std; const int MAXN = 2e6 + 6; int N, M; int arr[MAXN]; int A[MAXN]; int main() {     scanf("%d", &N);     arr[0] = -1;     for (int n = 0; n < N; n++) {         scanf("%d", &arr[2*n + 1]);         arr[2 * n + 2] = -1;     }     N = 2 * N + 1;       int r = 0, p = 0;     for (int n = 0; n < N; n++) {         if (n <= r) A[n] = min(A[2 * p - n], r - n);         while (n - A[n] - 1 >= 0 && n + A[n] + 1 < N && arr[n - A[n] - 1] == arr[n + A[n] + 1]) A[n]++;         if (r < n + A[n]) r = n + A[n], p = n;     }       scanf("%d", &M);     for (int m = 0; m < M; m++) {         int s, e;         scanf("%d%d", &s, &e);         int len = e - s + 1;         s--; s *= 2; s++;         e--; e *= 2; e++;         int mid = (s + e) >> 1;         printf("%d\n", A[mid] >= len ? 1 : 0);     }     return 0; } Colored by Color Scripter

cs