Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届决赛真题-三角序列(Java组)
题目 2742:

蓝桥杯2022年第十三届决赛真题-三角序列(Java组)

时间限制: 10s 内存限制: 1024MB 提交: 11 解决: 0

题目描述

给定 n 组成对的数 ai , bi,每组数表示一个 ai 行 ai 列的如图所示的三角形:

蓝桥杯2022年第十三届决赛真题-三角序列(Java组)1

其中 bi 为 0 时左边较低,为 1 时右边较低。 

将每组数对应的三角按数的顺序从左到右拼接起来。 

现给出 m 组询问 li ,ri , vi,对每组询问求最低高度 hi 使得 li 到 ri 列之间的高度在 hi 以内的 o 的数量大于等于 vi。 

输入格式

输入的第一行包含两个整数 n, m,用一个空格分隔。

接下来 n 行,每行包含两个整数 ai , bi,用一个空格分隔。

接下来 m 行,每行包含三个整数 li ,ri , vi,相邻两个整数之间用一个空格分隔。

输出格式

输出 m 行,每行包含一个整数 hi ,依次表示每次询问对应的答案。如果不存在这样的 hi,请输出 −1。

样例输入

6 6
3 0
4 0
2 1
3 1
5 0
1 1
3 9 12
3 9 13
3 4 4
14 16 7
9 15 12
1 18 42

样例输出

2
3
3
3
3
-1

提示

第一个询问对应的范围如图所示:

蓝桥杯2022年第十三届决赛真题-三角序列(Java组)2

对于 30% 的评测用例,1 ≤ n, m, ai ≤ 500; 

对于 50% 的评测用例,1 ≤ n, m, ai ≤ 5000; 

对于所有评测用例,1 ≤ n, m ≤ 200000 ,1 ≤ ai ≤ 106 ,0 ≤ bi ≤ 1 , 1 ≤ li ≤ ri ≤ ∑ ai ,1 ≤ vi ≤ 1018。 

标签