题目背景
感谢 Lotuses 提供的数据
题目描述
给定 n 组成对的数 ai,bi,每组数表示一个 ai 行 ai 列的如图所示的三角形:

其中 bi 为 0 时左边较低,为 1 时右边较低。
将每组数对应的三角按数的顺序从左到右拼接起来。
现给出 m 组询问 li,ri,vi,对每组询问求最低高度 hi 使得 li 到 ri 列之间的高度在 hi 以内的 o 的数量大于等于 vi。
输入格式
输入的第一行包含两个整数 n,m,用一个空格分隔。
接下来 n 行,每行包含两个整数 ai,bi,用一个空格分隔。
接下来 m 行,每行包含三个整数 li,ri,vi,相邻两个整数之间用一个空格分隔。
输出格式
输出一行包含一个字符串表示答案。
提示
【样例说明】
第一个询问对应的范围如图所示

【评测用例规模与约定】
- 对于 30% 的评测用例,1≤n,m,ai≤500;
- 对于 50% 的评测用例,1≤n,m,ai≤5000;
- 对于所有评测用例,1≤n,m≤2×105,1≤ai≤106,0≤bi≤1,1≤li≤ri≤∑ai,1≤vi≤1018。
蓝桥杯 2022 国赛 A 组 I 题。