#P15626. [2022年保加利亚国家队组队赛Junior]Trees树木

[2022年保加利亚国家队组队赛Junior]Trees树木

题目描述

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

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

如果猫所在的树高度为 hh、颜色为 cc,那么它可以看到:

  • 高度小于 hh 的树;
  • 高度等于 hh,且颜色不大于 cc 的树。

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

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

任务

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

函数接口

你需要实现如下函数:

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

其中:

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

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

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

树的编号从 11 到 NN。

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

数据范围

  • 1≤N≤1061 \le N \le 10^6;
  • 0≤hi,ci≤1050 \le h_i,c_i \le 10^5;
  • 约 26%26\% 的测试满足 N≤5×103N\le 5\times 10^3 且所有颜色均为 00;
  • 约 70%70\% 的测试满足 N≤105N\le 10^5 且所有颜色均为 00;
  • 约 83%83\% 的测试满足 N≤106N\le 10^6 且 ci≤10c_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}

示例解释

对于第 11 棵树,最远的可见树是第 99 棵树,它的高度为 22,颜色为 11,高度小于 3636。

注意第 1010 棵树虽然高度也为 3636,但颜色为 55,大于第 11 棵树的颜色 44,因此第 11 棵树看不到第 1010 棵树。

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

本地测试

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

本地 grader 的输入格式为:

  • 第一行一个整数 NN;
  • 接下来 NN 行,每行两个非负整数,表示对应树的高度和颜色。

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

@下发文件