#P18759. [2027年国家集训队互测] Task Scheduling

[2027年国家集训队互测] Task Scheduling

Task Scheduling

题目描述

一台机器上,有 nn 个无依赖关系的任务等待被调度。在 tt 时刻启动执行的任务,会在 t+1t+1 时刻完成。所有任务只能在整数时刻启动;一个任务完成时,可以立即启动另一个任务。在一个任务执行的过程中,无法执行别的任务。

任务具有时效性。可以被表示为:第 ii 个任务的启动时刻,必须在 lil_i 时刻到 rir_i 时刻(包含两边)之间。

此外,还有 mm 条约束。第 jj 个约束表示,在 pjp_j 时刻到 qjq_j 时刻(包含两边)之间,最多只能启动一个任务。

请确定每个任务的启动时刻,满足上述要求。

输入格式

本题包含多组测试数据。

输入的第一行包含非负整数 TT,表示测试数据组数。

接下来依次输入每组测试数据,对于每组测试数据:

  • 第一行包含两个整数 nn 和 mm。

  • 接下来 nn 行,每行两个整数 lil_i 和 rir_i,表示第 ii 个任务的可用时间区间。

  • 接下来 mm 行,每行两个整数 pjp_j 和 qjq_j,表示第 jj 个调度约束区间。

输出格式

对于每组数据,输出一行 nn 个整数,依次表示每个任务的启动时刻。特别地,若不存在可行方案,则输出 Impossible。若存在多组可行方案,输出任意一组即可。

样例一

样例输入

4
2 3
2 7
1 10
7 8
2 10
1 6
2 2
2 5
1 9
1 5
4 9
2 4
3 8
3 6
2 7
4 7
8 9
1 6
4 1
6 7
6 7
6 7
1 11
21 31

样例输出

7 1
3 9
8 6
Impossible

说明

本样例满足子任务 11 的限制。

  • 对于第一组数据,两个任务分别在时刻 7,17,1 启动。均在各自的 [l,r][l,r] 范围内,且满足所有约束。

  • 对于第四组数据,前三个任务都只能在时刻 66 或 77 启动。故不存在可行的方案。

样例二

见下发文件中的 ex_data2.in 和 ex_data2.ans。

本样例满足子任务 22 的限制。

样例三

见下发文件中的 ex_data3.in 和 ex_data3.ans。

本样例满足子任务 33 的限制。

样例四

见下发文件中的 ex_data4.in 和 ex_data4.ans。

本样例满足子任务 44 的限制。

样例五

见下发文件中的 ex_data5.in 和 ex_data5.ans。

本样例满足子任务 55 的限制。

样例六

见下发文件中的 ex_data6.in 和 ex_data6.ans。

本样例满足子任务 66 的限制。

样例七

见下发文件中的 ex_data7.in 和 ex_data7.ans。

本样例满足子任务 77 的限制。

样例八

见下发文件中的 ex_data8.in 和 ex_data8.ans。

本样例满足子任务 88 的限制。

数据范围

设 N,MN,M 分别为单个测试点内所有测试数据的 n,mn,m 的和。对于所有测试数据,均有:

  • $1 \le n \le 2.5 \times 10^5,0 \le m \le 2.5 \times 10^5$;

  • 1≤li≤ri≤1091 \le l_i \le r_i \le 10^{9};

  • 1≤pj≤qj≤1091 \le p_j \le q_j \le 10^{9}。

子任务编号 N≤N\le M≤M\le 特殊性质 分值
11 1010 无 55
22 2.5×1052.5\times 10^5 A\rm A
33 10310^3 B\rm B 1515
44 2.5×1052.5\times 10^5 C\rm C
55 10410^4 B\rm B
66 10510^5
77 无
88 2.5×1052.5\times 10^5

A\rm A:保证 n≤100n\le100,且对于所有 1≤i<n1\le i< n,均有 li≤li+1l_i\le l_{i+1},ri≤ri+1r_i\le r_{i+1}。

B\rm B:对于所有 1≤i≤n1\le i\le n,均有 ri≤5max⁡(n,m)r_i\le 5\max(n,m)。

C\rm C:对于所有 1≤i≤m1\le i\le m,均有 pi=i,qi=i+1p_i=i,q_i=i+1,且对于所有 1≤i≤n1\le i\le n,均有 ri≤mr_i\le m。

完整样例附件

全部 8 份样例见 样例 ZIP 附件,也可查看 所有样例。附件中的 .ans 为一组合法输出,答案不唯一。

TT 是非负整数,T=0T=0 合法,此时无需输出。所有输入均满足 N,M≤250000N,M\le250000。