题目描述

Deni 有一座美丽的花园，里面种着一排树。每棵树由两个整数描述：高度和颜色，也就是绿色的某种色调。

Deni 的猫 Xorange 很喜欢爬到树上向左、向右看。

如果猫所在的树高度为 $h$、颜色为 $c$，那么它可以看到：

• 高度小于 $h$ 的树；
• 高度等于 $h$，且颜色不大于 $c$ 的树。

对于猫所在的某一棵树，所有它能看到的树中，距离它最远的树称为这棵树对应的“有趣树”。如果最远的树不止一棵，则只把其中最靠左的一棵称为有趣树。

Deni 想知道：如果 Xorange 分别爬到每一棵树上，对应的有趣树分别是哪一棵。

任务

请实现函数 calc，帮助 Deni 求出所有有趣树。

函数接口

你需要实现如下函数：

vector<int> calc(int N, vector<int>& h, vector<int>& c);

其中：

• $N$ 表示树的数量；
• h[i] 表示第 $i+1$ 棵树的高度；
• c[i] 表示第 $i+1$ 棵树的颜色。

函数需要返回一个长度为 $N$ 的整数数组。第 $i$ 个返回值表示猫位于第 $i$ 棵树时，它对应的有趣树编号。

如果相对于某棵树不存在任何有趣树，则对应位置返回 0。

树的编号从 $1$ 到 $N$。

你的程序 trees.cpp 只需要实现函数 calc。可以包含其他辅助函数和全局变量，但不能包含 main 函数，也不能从标准输入读入或向标准输出输出。

数据范围

• $1 \le N \le 10^6$；
• $0 \le h_i,c_i \le 10^5$；
• 约 $26\%$ 的测试满足 $N\le 5\times 10^3$ 且所有颜色均为 $0$；
• 约 $70\%$ 的测试满足 $N\le 10^5$ 且所有颜色均为 $0$；
• 约 $83\%$ 的测试满足 $N\le 10^6$ 且 $c_i\le 10$。

示例通信

评测程序调用：

calc(10,
     {36, 18, 36, 0, 43, 46, 36, 3, 2, 36},
     {4, 1, 3, 2, 2, 1, 4, 0, 1, 5})

你的函数应返回：

{9, 9, 9, 0, 10, 1, 1, 4, 4, 1}

示例解释

对于第 $1$ 棵树，最远的可见树是第 $9$ 棵树，它的高度为 $2$，颜色为 $1$，高度小于 $36$。

注意第 $10$ 棵树虽然高度也为 $36$，但颜色为 $5$，大于第 $1$ 棵树的颜色 $4$，因此第 $1$ 棵树看不到第 $10$ 棵树。

第 $4$ 棵树不存在有趣树，因为它左右都没有高度更小的树，也没有高度相同且颜色不大于它的树。

本地测试

原题提供 Lgrader.cpp 进行本地测试。将本地 grader 与你的 trees.cpp 放在同一目录下，只编译 Lgrader.cpp 即可。

本地 grader 的输入格式为：

• 第一行一个整数 $N$；
• 接下来 $N$ 行，每行两个非负整数，表示对应树的高度和颜色。

输出为你的函数返回的有趣树编号序列。

@下发文件