A13294 | Bombs
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You are given a permutation, $p_1, p_2, \ldots, p_n$ .
Imagine that some positions of the permutation contain bombs, such that there exists at least one position without a bomb.
For some fixed configuration of bombs, consider the following process. Initially, there is an empty set, $A$ .
For each $i$ from $1$ to $n$ :
- Add $p_i$ to $A$ .
- If the $i$ -th position contains a bomb, remove the largest element in $A$ .
After the process is completed, $A$ will be non-empty. The cost of the configuration of bombs equals the largest element in $A$ .
You are given another permutation, $q_1, q_2, \ldots, q_n$ .
For each $1 \leq i \leq n$ , find the cost of a configuration of bombs such that there exists a bomb in positions $q_1, q_2, \ldots, q_{i-1}$ .
For example, for $i=1$ , you need to find the cost of a configuration without bombs, and for $i=n$ , you need to find the cost of a configuration with bombs in positions $q_1, q_2, \ldots, q_{n-1}$ .
Imagine that some positions of the permutation contain bombs, such that there exists at least one position without a bomb.
For some fixed configuration of bombs, consider the following process. Initially, there is an empty set, $A$ .
For each $i$ from $1$ to $n$ :
- Add $p_i$ to $A$ .
- If the $i$ -th position contains a bomb, remove the largest element in $A$ .
After the process is completed, $A$ will be non-empty. The cost of the configuration of bombs equals the largest element in $A$ .
You are given another permutation, $q_1, q_2, \ldots, q_n$ .
For each $1 \leq i \leq n$ , find the cost of a configuration of bombs such that there exists a bomb in positions $q_1, q_2, \ldots, q_{i-1}$ .
For example, for $i=1$ , you need to find the cost of a configuration without bombs, and for $i=n$ , you need to find the cost of a configuration with bombs in positions $q_1, q_2, \ldots, q_{n-1}$ .
输入格式
The first line contains a single integer, $n$ ( $2 \leq n \leq 300\,000$ ).
The second line contains $n$ distinct integers $p_1, p_2, \ldots, p_n$ ( $1 \leq p_i \leq n)$ .
The third line contains $n$ distinct integers $q_1, q_2, \ldots, q_n$ ( $1 \leq q_i \leq n)$ .
The second line contains $n$ distinct integers $p_1, p_2, \ldots, p_n$ ( $1 \leq p_i \leq n)$ .
The third line contains $n$ distinct integers $q_1, q_2, \ldots, q_n$ ( $1 \leq q_i \leq n)$ .
输出格式
Print $n$ space-separated integers, such that the $i$ -th of them equals the cost of a configuration of bombs in positions $q_1, q_2, \ldots, q_{i-1}$ .
输入输出样例
输入 #1
3 3 2 1 1 2 3
输出 #1
3 2 1
输入 #2
6 2 3 6 1 5 4 5 2 1 4 6 3
输出 #2
6 5 5 5 4 1
In the first test:
- If there are no bombs, $A$ is equal to $\{1, 2, 3\}$ at the end of the process, so the cost of the configuration is $3$ .
- If there is one bomb in position $1$ , $A$ is equal to $\{1, 2\}$ at the end of the process, so the cost of the configuration is $2$ ;
- If there are two bombs in positions $1$ and $2$ , $A$ is equal to $\{1\}$ at the end of the process, so the cost of the configuration is $1$ .
In the second test:
Let's consider the process for $i = 4$ . There are three bombs on positions $q_1 = 5$ , $q_2 = 2$ , and $q_3 = 1$ .
At the beginning, $A = \{\}$ .
- Operation $1$ : Add $p_1 = 2$ to $A$ , so $A$ is equal to $\{2\}$ . There exists a bomb in position $1$ , so we should delete the largest element from $A$ . $A$ is equal to $\{\}$ .
- Operation $2$ : Add $p_2 = 3$ to $A$ , so $A$ is equal to $\{3\}$ . There exists a bomb in position $2$ , so we should delete the largest element from $A$ . $A$ is equal to $\{\}$ .
- Operation $3$ : Add $p_3 = 6$ to $A$ , so $A$ is equal to $\{6\}$ . There is no bomb in position $3$ , so we do nothing.
- Operation $4$ : Add $p_4 = 1$ to $A$ , so $A$ is equal to $\{1, 6\}$ . There is no bomb in position $4$ , so we do nothing.
- Operation $5$ : Add $p_5 = 5$ to $A$ , so $A$ is equal to $\{1, 5, 6\}$ . There exists a bomb in position $5$ , so we delete the largest element from $A$ . Now, $A$ is equal to $\{1, 5\}$ .
- Operation $6$ : Add $p_6 = 4$ to $A$ , so $A$ is equal to $\{1, 4, 5\}$ . There is no bomb in position $6$ , so we do nothing.
In the end, we have $A = \{1, 4, 5\}$ , so the cost of the configuration is equal to $5$ .
- If there are no bombs, $A$ is equal to $\{1, 2, 3\}$ at the end of the process, so the cost of the configuration is $3$ .
- If there is one bomb in position $1$ , $A$ is equal to $\{1, 2\}$ at the end of the process, so the cost of the configuration is $2$ ;
- If there are two bombs in positions $1$ and $2$ , $A$ is equal to $\{1\}$ at the end of the process, so the cost of the configuration is $1$ .
In the second test:
Let's consider the process for $i = 4$ . There are three bombs on positions $q_1 = 5$ , $q_2 = 2$ , and $q_3 = 1$ .
At the beginning, $A = \{\}$ .
- Operation $1$ : Add $p_1 = 2$ to $A$ , so $A$ is equal to $\{2\}$ . There exists a bomb in position $1$ , so we should delete the largest element from $A$ . $A$ is equal to $\{\}$ .
- Operation $2$ : Add $p_2 = 3$ to $A$ , so $A$ is equal to $\{3\}$ . There exists a bomb in position $2$ , so we should delete the largest element from $A$ . $A$ is equal to $\{\}$ .
- Operation $3$ : Add $p_3 = 6$ to $A$ , so $A$ is equal to $\{6\}$ . There is no bomb in position $3$ , so we do nothing.
- Operation $4$ : Add $p_4 = 1$ to $A$ , so $A$ is equal to $\{1, 6\}$ . There is no bomb in position $4$ , so we do nothing.
- Operation $5$ : Add $p_5 = 5$ to $A$ , so $A$ is equal to $\{1, 5, 6\}$ . There exists a bomb in position $5$ , so we delete the largest element from $A$ . Now, $A$ is equal to $\{1, 5\}$ .
- Operation $6$ : Add $p_6 = 4$ to $A$ , so $A$ is equal to $\{1, 4, 5\}$ . There is no bomb in position $6$ , so we do nothing.
In the end, we have $A = \{1, 4, 5\}$ , so the cost of the configuration is equal to $5$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted