#A. [JRKSJ R9] ZYPRESSEN

    Type: RemoteJudge 4000ms 2048MiB

[JRKSJ R9] ZYPRESSEN

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

长夜伴浪破晓梦,梦晓破浪伴夜长。

已经完全是秋季了。

即使如此,丝柏(ZYPRESSEN)也是一如既往的黢黑吧。

题目描述

给你一个长度为 nn 的序列 aa,共有 qq 次询问,每次询问如下:

  • 给你一个区间 [l,r][l,r],对于所有的 i,j,ki,j,k 满足 li<j<krl\le i<j<k\le r 且三边长度分别为 ai,aj,aka_i,a_j,a_k 的三角形存在,你需要求出 ai+aj+aka_i+a_j+a_k 的最小值。

三边长度分别为 a,b,c(abc)a,b,c(a\le b\le c) 时,能构成三角形当且仅当 a+b>ca+b>c

输入格式

第一行两个整数 n,qn,q

第二行 nn 个整数 a1na_{1\dots n}

接下来 qq 行,每行两个整数 l,rl,r 表示询问。

输出格式

qq 行,每行一个整数表示答案。如果不存在符合条件的 i,j,ki,j,k,输出 yumi!

7 6
3 11 1 5 12 19 10
1 1
3 5
2 5
1 7
2 6
1 4
yumi!
yumi!
28
24
28
yumi!
20 20
26 17 11 89 56 33 72 73 43 77 80 87 97 17 43 74 72 91 49 69
10 19
2 4
3 5
2 11
1 12
10 19
3 5
8 15
8 12
14 20
5 11
13 18
2 18
17 19
1 9
5 8
9 12
1 11
4 13
3 18
109
yumi!
yumi!
87
54
109
yumi!
103
193
109
132
163
45
212
54
161
200
54
132
87

提示

样例解释 1

对于区间 [3,5][3,5],因为 1+5<121+5<12,所以不存在合法的三角形。

对于区间 [2,5][2,5][2,6][2,6],选取 ai=11,aj=5,ak=12a_i=11,a_j=5,a_k=12

对于区间 [1,7][1,7],选取 ai=3,aj=11,ak=10a_i=3,a_j=11,a_k=10

数据规模与约定

本题采用捆绑测试。

Subtask\mathrm{Subtask} nn\le qq\le 特殊性质 分数
11 5×1035\times 10^3 1010
22 5×1045\times 10^4 2525
33 2.5×1052.5\times 10^5 5×1055\times 10^5 \checkmark 1010
44 5555

特殊性质:保证 aia_i 在范围内等概率随机生成。

对于所有数据,保证 1n2.5×1051\le n\le 2.5\times 10^51q5×1051\le q\le 5\times 10^51ai1071\le a_i\le 10^71lrn1\le l\le r\le n

周五分享

Not Attended
Status
Done
Rule
IOI
Problem
2
Start at
2024-9-20 14:00
End at
2024-9-24 14:00
Duration
96 hour(s)
Host
Partic.
17