Distinct Elements on Subsegments

AtCoder

IDagc059_d

Time2000ms

Memory256MB

Difficulty—

For an integer array $A=(A_1, A_2, \ldots, A_{N + K-1})$ ($1 \leq A_i \leq N+K-1$), let's construct an array $B=(B_1, B_2, \ldots, B_N)$, where $B_i$ is the number of distinct elements in $A_i,A_{i+1},\ldots,A_{i+K-1}$. You are given $B_1, B_2, \ldots, B_N$. Determine if there exists an array $A$ which could have produced such an array $B$, and if yes, construct one. Solve $T$ test cases for each input file. ## Constraints * $1 \le T \le 5 \cdot 10^4$ * $2 \le N \le 2 \cdot 10^5$ * $2 \le K \le 2 \cdot 10^5$ * $1 \le B_i \le K$ * The sum of $N$ in one input file doesn't exceed $2\cdot 10^5$. * The sum of $K$ in one input file doesn't exceed $2\cdot 10^5$. * All values in the input are integers. ## Input Input is given from Standard Input in the following format: $T$ $case_1$ $case_2$ $\vdots$ $case_T$ Each case is in the following format: $N$ $K$ $B_1$ $B_2$ $\ldots$ $B_N$ [samples]

Samples

Input #1

3
3 3
1 2 1
4 3
1 2 2 1
6 4
3 3 3 3 3 3

Output #1

NO
YES
1 1 1 2 2 2 
YES
1 2 3 1 2 3 1 2 3

API Response (JSON)

{
  "problem": {
    "name": "Distinct Elements on Subsegments",
    "description": {
      "content": "For an integer array $A=(A_1, A_2, \\ldots, A_{N + K-1})$ ($1 \\leq A_i \\leq N+K-1$), let's construct an array $B=(B_1, B_2, \\ldots, B_N)$, where $B_i$ is the number of distinct elements in $A_i,A_{i+1}",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc059_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For an integer array $A=(A_1, A_2, \\ldots, A_{N + K-1})$ ($1 \\leq A_i \\leq N+K-1$), let's construct an array $B=(B_1, B_2, \\ldots, B_N)$, where $B_i$ is the number of distinct elements in $A_i,A_{i+1}...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments