孤独（Solitude）

Luogu

IDLGP10705

Time2000ms

Memory512MB

DifficultyP5

给出 $n$ 和 $n$ 个整数 $a_i$（$1\le i\le n$），$n$ 个整数 $b_i$（$1\le i\le n$）。现在对于一个长为 $n$ 的序列 $S$ 有以下规定： - $S_i=a_i$ 或 $b_i$。 - 对于所有的 $S_i$（$1\le i\le n$），若 $S_i>S_{i-1}$ 且 $S_i>S_{i+1}$ 那么称 $S_i$ 为**峰**，特别地 $S_0=S_{n+1}=0$。 **现求：最大峰数以及取到最大峰数时的最大极差。** **极差：一个序列中最大值和最小值的差。** **updated：$S_0$ 和 $S_{n+1}$ 不参与极差运算。** ## Input 第一行一个整数 $n$。第二行 $n$ 个整数，表示 $a_1,a_2\dots a_n$。第三行 $n$ 个整数，表示 $b_1,b_2\dots b_n$。 ## Output 输出共两行。第一行一个整数表示**最大峰数**。第二行一个整数表示**取到最大峰数时的最大极差**。 [samples] ## Background >$$行走的岁月静好，$$ > >$$苍青的天空古老。$$ > >$$轻轻唱起，$$ > >$$那只风鸟。$$ > >$$你却不见了。$$ ## Note #### 【样例解释】样例一中 $S$ 序列的一种合法方案为 $9,1,2,4,1,10$。其中 $S_1,S_4,S_6$ 为**峰**，最大值为 $10-1=9$。 #### 【数据范围】 | subtask 编号 | $n$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | | $0$ | $\le 20$ | $-$ | $10$ | | $1$ | $\le 2000$ | $-$ | $10$ | | $2$ | $\le 10^5$ | $A$ | $10$ | | $3$ | $\le 10^5$ | $B$ | $10$ | | $4$ | $\le 10^5$ | $C$ | $10$ | | $5$ | $\le 5\times10^5$ | $-$ | $50$ | 特殊性质 $A$：$\forall 1< i\le n$，$\text{max}(a_{i-1},b_{i-1})\le \text{min}(a_i,b_i)$。特殊性质 $B$：$\forall 1< i\le n$，$\text{min}(a_i,b_i)\le\text{max}(a_{i-1},b_{i-1})\le\text{max}(a_i,b_i)$。特殊性质 $C$：$\forall 1\le i\le n$，$a_i=k$，$k$ 是一个正整数。对于 $100\%$ 的数据，$1\le n\le 5\times10^5$，$1\le a_i,b_i\le 10^9$，保证 $a_i\ne b_i$。 **特别提醒：本题使用 subtask 捆绑测试，只有通过一个子任务的全部测试点才能获得此子任务的分数。**

Samples

Input #1

6
9 1 2 4 7 10 
8 10 5 1 1 7

Output #1

3
9

Input #2

10
6 13 27 31 34 59 64 66 71 95 
4 4 10 22 26 28 46 55 62 68

Output #2

5
91

API Response (JSON)

{
  "problem": {
    "name": "孤独（Solitude）",
    "description": {
      "content": "给出 $n$ 和 $n$ 个整数 $a_i$（$1\\le i\\le n$），$n$ 个整数 $b_i$（$1\\le i\\le n$）。 现在对于一个长为 $n$ 的序列 $S$ 有以下规定： - $S_i=a_i$ 或 $b_i$。 - 对于所有的 $S_i$（$1\\le i\\le n$），若 $S_i>S_{i-1}$ 且 $S_i>S_{i+1}$ 那么称 $S_i$ 为**峰**，特别",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10705"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给出 $n$ 和 $n$ 个整数 $a_i$（$1\\le i\\le n$），$n$ 个整数 $b_i$（$1\\le i\\le n$）。\n\n现在对于一个长为 $n$ 的序列 $S$ 有以下规定：\n\n- $S_i=a_i$ 或 $b_i$。\n\n- 对于所有的 $S_i$（$1\\le i\\le n$），若 $S_i>S_{i-1}$ 且 $S_i>S_{i+1}$ 那么称 $S_i$ 为**峰**，特别...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments