QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
[+17]

# 7980. 区间切割

Statistics

n 个区间 [Li,Ri],然后有 m 次切割操作,每次操作由三元组 (x,l,r) 描述,对 i[l,r] 进行如下操作:

  • 如果 x[Li,Ri],什么都不做。
  • 否则区间 i 将被切割为 [Li,x][x,Ri] 两段,用较长的一段作为新的区间 i,如果长度相等选择 [Li,x]

求出每个区间在所有操作后的左右端点。为了简化问题,保证所有 x 构成 1m 的排列。

输入格式

第一行包含三个整数 n,m,id (1n105,1m106,0id7),其中 id 表示子任务编号,样例中 id=0

接下来 n 行,每行包含两个整数 Li,Ri (1Li<Rim),表示区间 i 的左右端点。

接下来 m 行,每行包含三个整数 x,l,r (1xm,1lrn),表示一次切割操作。保证所有 x 构成 1m 的排列。

输出格式

n 行,第 i 行包含两个整数表示线段 i 最终的左右端点。

样例输入 #1
1 4 0
1 4
1 1 1
4 1 1
3 1 1
2 1 1
样例输出 #1
1 2
样例输入 #2
5 5 0
2 3
4 5
1 4
2 5
2 4
1 5 5
2 5 5
3 1 1
5 4 5
4 2 2
样例输出 #2
2 3
4 5
1 4
2 5
2 4
样例输入/输出 #3

ex_cut3.in/out,满足子任务 2 的限制。

样例输入/输出 #4

ex_cut4.in/out,满足子任务 3 的限制。

数据范围

对于全部数据

1n105,1m106

1Li<Rim,1xm,1lrn,保证所有 x 构成 1m 的排列。

子任务分值nm特殊性质
1550005000
215160002×105AB
315105106A
415160002×105B
510105106B
620160002×105
720105106

特殊性质 A:所有 x 构成 1m 的随机排列。

特殊性质 B:每次操作的 l=1,r=n