atcoder#ABC196E. [ABC196E] Filters

[ABC196E] Filters

题目描述

整数列 $ A\ =\ (a_1,\ a_2,\ \dots,\ a_N),\ T\ =\ (t_1,\ t_2,\ \dots,\ t_N),\ X\ =\ (x_1,\ x_2,\ \dots,\ x_Q) $ が与えられます。
N N 個の関数 f1(x), f2(x), , fN(x) f_1(x),\ f_2(x),\ \dots,\ f_N(x) を、

$ f_i(x)\ =\ \begin{cases}\ x\ +\ a_i\ &\ (t_i\ =\ 1)\\ \max(x,\ a_i)\ &\ (t_i\ =\ 2)\\ \min(x,\ a_i)\ &\ (t_i\ =\ 3)\\ \end{cases} $

と定義します。

i = 1, 2, , Q i\ =\ 1,\ 2,\ \dots,\ Q のそれぞれについて、 fN(  f2(f1(xi))  ) f_N(\ \dots\ f_2(f_1(x_i))\ \dots\ ) を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

N N a1 a_1 t1 t_1 a2 a_2 t2 t_2 \vdots aN a_N tN t_N Q Q x1 x_1 x2 x_2 \cdots xQ x_Q

输出格式

Q Q 行にかけて出力せよ。 i i 行目には、 fN(  f2(f1(xi))  ) f_N(\ \dots\ f_2(f_1(x_i))\ \dots\ ) を出力せよ。

题目大意

题目描述

给出整数数列 A=(a1,a2,...,an)A=(a_1,a_2,...,a_n)T=(t1,t2,...,tn)T=(t_1,t_2,...,t_n)X=(x1,x2,...,xq)X=(x_1,x_2,...,x_q)

定义 nn 个函数 f1(x),f2(x),...,fn(x)f_1(x),f_2(x),...,f_n(x)

$$f_i(x)=\begin{cases} x+a_i& t_i=1\\ \max(x,a_i)& t_i=2\\ \min(x,a_i)& t_i=3\\ \end{cases} $$

对于 i=1,2,...,qi=1,2,...,q,求出 fn(...f2(f1(xi))...)f_n(...f_2(f_1(x_i))...) 的值。

输入格式

第一行一个整数 nn,为函数的个数。

接下来 nn 行每行两个整数 ai,tia_i,t_i,含义如题面所示。

下一行有一个整数 qq,为需要求值的点数。

接下来一行 qq 个整数,第 ii 个数为 xix_i

输出格式

输出qq 行,第 ii 行为 fn(...f2(f1(xi))...)f_n(...f_2(f_1(x_i))...) 的值。

数据范围

对于 100%100\% 的数据所有输入的值均为整数,1n,q2×1051 \leqslant n,q \leqslant 2 \times 10^51ti31 \leqslant t_i \leqslant 3ai,xi109|a_i|,|x_i| \leqslant 10^9

3
-10 2
10 1
10 3
5
-15 -10 -5 0 5
0
0
5
10
10

提示

制約

  • 入力は全て整数
  • 1 < = N < = 2 × 105 1\ <\ =\ N\ <\ = 2\ \times\ 10^5
  • 1 < = Q < = 2 × 105 1\ <\ =\ Q\ <\ = 2\ \times\ 10^5
  • ai < = 109 |a_i|\ <\ =\ 10^9
  • 1 < = ti < = 3 1\ <\ = t_i\ <\ = 3
  • xi < = 109 |x_i|\ <\ =\ 10^9

Sample Explanation 1

$ f_1(x)\ =\ \max(x,\ -10),\ f_2(x)\ =\ x\ +\ 10,\ f_3(x)\ =\ \min(x,\ 10) $ です。 したがって、 - f3(f2(f1(15))) = 0 f_3(f_2(f_1(-15)))\ =\ 0 - f3(f2(f1(10))) = 0 f_3(f_2(f_1(-10)))\ =\ 0 - f3(f2(f1(5))) = 5 f_3(f_2(f_1(-5)))\ =\ 5 - f3(f2(f1(0))) = 10 f_3(f_2(f_1(0)))\ =\ 10 - f3(f2(f1(5))) = 10 f_3(f_2(f_1(5)))\ =\ 10 となります。