分数: 525 点
问题陈述
某个冰箱为每种饮料分配了一个 6- 数字字符串作为其 ID。
这台冰箱储存 N 饮料。 的 i-th 饮料有 ID S_i 和尺寸 V_i. S_1, \dots, S_N 是不同的。
答案 Q 查询。每个查询都以以下形式给出 6- 数字字符串 x, y,并询问以下问题。
- 在此冰箱中存储的饮料中,找到分配了 ID 的饮料的尺寸总和 s 满足以下每个 k = 1, \dots, 6.
- x_k \leq s_k \leq y_k,其中 s_k, x_k, y_k 表示由 k第 位数字 s, x, y。
约束
- N 是一个整数。
- 1 \leq N \leq 3 \times 10^5
- S_i 是由数字 (
0-9). - |S_i| = 6
- S_1, \dots, S_N 是不同的。
- V_i 是一个整数。
- 1 \leq V_i \leq 10^9
- Q 是一个整数。
- 1 \leq Q \leq 3 \times 10^5
- 在每个查询中, x 和 y 是由数字 (
0-9). - 在每个查询中, |x| = |y| = 6.
输入
输入由标准输入按以下格式给出:
N
S_1 V_1
\dots
S_N V_N
Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q
在这里, \mathrm{query}_q 是 q-第一个查询,按以下格式给出:
x y
输出
输出 Q 行。的 q- 第行应包含以下问题的答案 q第一个查询。
示例输入 1
5 000000 1 314159 2 161803 10 169231 5 384400 20 4 150001 269944 302010 396939 000000 999999 999000 000444
示例输出 1
15 0 38 0
对于第一个查询,满足条件的饮料是第三和第四饮料。
对于第二个查询,没有饮料满足条件。
对于第三个查询,满足条件的饮料是第一、第二、第三、第四、第五饮料。
对于第四个查询,没有饮料满足条件。
示例输入 2
8 778722 12744734 488742 359266786 955942 335004463 454854 331175626 934246 179761526 927777 657312747 652568 109900930 753279 405123850 8 201000 785589 202325 955898 310401 875947 044023 988999 111230 567897 133241 577989 101033 999499 453013 796988
示例输出 2
515024780 109900930 0 331175626 331175626 331175626 584885376 331175626