A30285. 两个序列的故事

两个序列的故事

题目描述

给定两个整数序列 A = a₁,a₂,,,,a_n 与 B = b₁,b₂,,,,b_n , 我们称 A 中长度为 ( r-l+1 )的连续子序列 a_l,a_l+1,,,,a_n (1 ≤ l ≤ r ≤ n) 是好的，如果 min(a_l , a_l+1 , …, a_r ) ≥ b_r-l + 1 。

对于所有 1 ≤ k ≤ n 请求出 A 中是否有长度为 k 的好的连续子序列。

时间限制： 11000        内存限制： 262144

输入

第一行输入一个整数 n (1 ≤ n ≤ 500000 ) 表示两个序列的长度。

第二行输入 n 个整数 a₁,a₂,,,,a_n (1 ≤ a_i ≤ 1000000 ) 表示序列 A。

第三行输入 n 个整数 b₁,b₂,,,,b_n (1 ≤ b_i ≤10⁶ ) 表示序列 B。

输出

在一行中输出长度为 n 的字符串 s₁,s₂,,,,s_n 。

若 A 中存在长度为 k 的好的连续子序列则 s_k = 1 ，否则 s_k = 0。

样例输入

样例#1：

5
1 3 2 5 3
6 3 3 2 3

样例#2：

1
1000000
1000000

样例#3：

1
1
1000000

样例输出

样例#1：

01010

样例#2：

1

样例#3：

0