28222번 - Sequence 서브태스크다국어언어 제한함수 구현

In the enchanting realm of APIO, there lived a young and brilliant student named Alice. Alice had an insatiable curiosity for solving intriguing problems that challenged her mathematical prowess. One day, she stumbled upon a mystical series of numbers with a length of $N$ (that is $A[0]$, $A[1]$, $\cdots$, $A[N - 1]$), and she couldn't resist the allure of exploring its secrets.

Here, she wants to share with you some of her discoveries. But before that, for your convenience, we need to define some things:

• Define $W(l, r,x)$ as $\displaystyle\sum_{i=l}^{r}{\mathrm{I}[A[i] = x]}$, i.e., the number of occurrences of $x$ in $A[l] \cdots A[r]$.
• Define the set of medians of a non-empty integer sequence $B[0]$ $B[1]$ $\cdots$ $B[k - 1]$ as $S(\{B[0], B[1], \cdots ,B[k - 1]\})$, and in the following Alice will show you how to calculate the set of medians step-by-step:
  • First, sort the elements $B[0], B[1], \cdots ,B[k - 1]$ in ascending order to obtain the sequence $C[0], C[1], \cdots ,C[k - 1]$.
  • Then, $S(\{B[0], B[1], \cdots ,B[k - 1]\}) = \{C[\lfloor \frac{k-1}{2} \rfloor ], C[\lceil \frac{k-1}{2} \rceil ] \}$.
  • To enhance your understanding of the calculation of S$, let's consider a few examples:
    • $S(\{6, 3, 5, 4, 6, 2, 3\}) = \{4\}$.
    • $S(\{4, 2, 3, 1\}) = \{2, 3\}$.
    • $S(\{5, 4, 2, 4\}) = \{4\}$.

Alice is eager to find the maximum value of $\displaystyle\max_{x \in S(l,r)}{W(l, r,x)}$, where $0 ≤ l ≤ r ≤ N - 1$, as it poses a challenging task. The term $S(l, r)$ represents the set of medians derived from $A[l] \cdots A[r]$ (as previously mentioned as $S(A[l], \cdots ,A[r])$). Although Alice has already obtained the answer, she seeks assistance in verifying it and kindly requests your help in programming the calculation.

You should implement the following procedure:

int sequence(int N, std::vector<int> A);

• $N$: the length of sequence $A$.
• $A$: array of length $N$, describing the sequence $A$.
• This procedure should return an integer representing the maximum value among all possible pairs $(l, r)$.
• This procedure is called exactly once.

• $1 ≤ N ≤ 5 \times 10^5$
• $1 ≤ A[i] ≤ N$

Consider the following call:

sequence(7, {1, 2, 3, 1, 2, 1, 3});

This procedure should return $3$.

In this case, $S(0, 5) = \{1, 2\}$, $W(0, 5, 1) = 3$, $W(0, 5, 2) = 2$. So the value of $(0, 5)$ is $3$.

It is easy to verify that $(0, 5)$ has the greatest value among all possible pairs.

Consider the following call:

sequence(9, {1, 1, 2, 3, 4, 3, 2, 1, 1});

This procedure should return 2.

Consider the following call:

sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2});

This procedure should return $3$.

The sample grader reads input in the following format:

• Line $1$: $N$
• Line $2$: $A[0]$ $A[1]$ $\cdots$ $A[N - 1]$.

The sample grader prints your output in the following format:

• Line $1$: the return value of sequence.

• compile_cpp.sh grader.cpp run_cpp.sh sequence.cpp sequence.h
• sample-1.in sample-1.out sample-2.in sample-2.out sample-3.in sample-3.out