[2019年3月雅礼集训]duliu
题目描述
有 n 道题,编号为 1 到 n,第 i 道题的难度为 di。定义两道题 j,k 的函数值为
f(j,k)=dj+dk.
给定 m 次询问。每次询问给出 l,r,x,你需要选择一个非空连续区间 [a,b],满足 l≤a≤b≤r,并且
j=a∑bk=a∑bf(j,k)≥x.
求所选区间中最大难度 maxa≤i≤bdi 的最小可能值。如果不存在满足条件的区间,输出 −1。
这里 j,k 独立遍历整个区间,计算的是所有有序题目对,包含 j=k 的情况。因此,上面的求和也等于
2(b−a+1)i=a∑bdi.
每次询问独立,不改变题目的难度。
输入格式
第一行两个整数 n,m,分别表示题目数量和询问数量。
第二行 n 个正整数 d1,d2,…,dn。
接下来 m 行,每行三个整数 l,r,x,表示一次询问。
输出格式
对于每次询问,输出一行一个整数,表示答案;若无解,输出 −1。
样例输入 1
5 2
1 1 2 3 4
1 5 2
1 5 11
样例输出 1
1
2
样例输入 2
5 4
1 3 2 4 6
1 3 3
1 3 2
2 4 10
1 1 1556528051
样例输出 2
2
1
3
-1
数据范围
所有数据满足 1≤n≤3×105,0≤m≤3×105,1≤di≤107,1≤l≤r≤n,1≤x≤1018。
| 子任务 |
分值 |
附加限制 |
| 1 |
6 分 |
n,m≤300 |
| 2 |
15 分 |
n,m≤5000 |
| 3 |
18 分 |
n,m≤50000 |
| 4 |
1 分 |
m=0 |
| 5 |
所有 di≤1 |
| 6 |
10 分 |
所有 di≤2 |
| 7 |
11 分 |
所有 di≤3 |
| 8 |
7 分 |
所有询问的 x=1 |
| 9 |
11 分 |
所有询问的 l=1,r=n |
| 10 |
20 分 |
无 |