305565: CF1055E. Segments on the Line
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Segments on the Line
题意翻译
给定 $n$ 个点,以及 $s$ 条线段,选择 $m$ 条线段,使得至少被一个线段覆盖的点的权值从小到大排序后,排名为 $k$ 的点的权值最小,若不可能产生 $k$ 个覆盖的点则输出 $-1$。 **【输入】** 第一行,四个数 $n,s,m,k$。 第二行,$n$ 个数表示点的坐标。 接下来 $s$ 行,每行两个数表示每条线段的左右端点。题目描述
You are a given a list of integers $ a_1, a_2, \ldots, a_n $ and $ s $ of its segments $ [l_j; r_j] $ (where $ 1 \le l_j \le r_j \le n $ ). You need to select exactly $ m $ segments in such a way that the $ k $ -th order statistic of the multiset of $ a_i $ , where $ i $ is contained in at least one segment, is the smallest possible. If it's impossible to select a set of $ m $ segments in such a way that the multiset contains at least $ k $ elements, print -1. The $ k $ -th order statistic of a multiset is the value of the $ k $ -th element after sorting the multiset in non-descending order.输入输出格式
输入格式
The first line contains four integers $ n $ , $ s $ , $ m $ and $ k $ ( $ 1 \le m \le s \le 1500 $ , $ 1 \le k \le n \le 1500 $ ) — the size of the list, the number of segments, the number of segments to choose and the statistic number. The second line contains $ n $ integers $ a_i $ ( $ 1 \le a_i \le 10^9 $ ) — the values of the numbers in the list. Each of the next $ s $ lines contains two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le n $ ) — the endpoints of the segments. It is possible that some segments coincide.
输出格式
Print exactly one integer — the smallest possible $ k $ -th order statistic, or -1 if it's impossible to choose segments in a way that the multiset contains at least $ k $ elements.
输入输出样例
输入样例 #1
4 3 2 2
3 1 3 2
1 2
2 3
4 4
输出样例 #1
2
输入样例 #2
5 2 1 1
1 2 3 4 5
2 4
1 5
输出样例 #2
1
输入样例 #3
5 3 3 5
5 5 2 1 1
1 2
2 3
3 4
输出样例 #3
-1