[SGU516] Schedule

题目描述

王国的皇家卫士轮流承担国王的警卫工作，在任意时刻恰好有一名卫士值班。

新的劳动规定要求实行五天工作制：每周一至周五的 09:00 到 18:00 为正常工作时间，其余时间均为非工作时间。一个日历周从周一 00:00 开始，到周日 24:00 结束。对于任意一名卫士，在任意一个日历周内，他承担警卫工作的非工作时间不能超过 $T$ 小时。

你得到了一份初始值班表以及若干次对值班表的修改。你只关心固定时间区间 $[T_1,T_2)$ 内的值班情况，并忽略这个区间之外的工作。

初始值班表由若干个时间点 $D_i$ 描述：从 $D_i$ 开始由给定卫士值班，直到下一名卫士接班。

之后有 $M$ 次修改。第 $i$ 次修改在时刻 $A_i$ 生效，它把值班表中时间区间 $[B_i,E_i)$ 整段改为由指定卫士值班，区间外的安排保持不变。修改按 $A_i$ 的非降序给出；若多次修改在同一时刻生效，则按照输入顺序依次执行。

注意，这里的问题并不是判断某一个时刻正在值班的卫士是否合法。对于每个现实时间点，都存在一份“当前版本”的完整值班表；我们需要判断这份当前值班表在整个 $[T_1,T_2)$ 上是否满足上述每周非工作时间限制。

求在现实时间区间 $[T_1,T_2)$ 内，有多大比例的时间里，当前版本的完整值班表是合法的。

输入格式

第一行包含三个整数 $N,M,T$：

• $1\le N\le10^5$，表示初始值班表的条目数；
• $0\le M\le10^5$，表示修改次数；
• $0\le T\le123$，表示每名卫士每周最多允许承担的非工作时间（小时）。

第二行包含两个日期时间 $T_1,T_2$，保证 $T_1<T_2$。

接下来 $N$ 行描述初始值班表。每行包含一个日期时间 $D_i$ 和一个卫士姓名。所有 $D_i$ 严格递增，并保证 $D_1\le T_1$。从 $D_i$ 开始由该卫士值班，直到下一条记录的时间。

接下来 $M$ 行描述修改。每行依次包含日期时间 $A_i,B_i,E_i$ 和一个卫士姓名，表示该修改在 $A_i$ 生效，并把 $[B_i,E_i)$ 改为由该卫士值班。保证 $A_i\le B_i<E_i$，且 $A_i$ 按非降序排列。

卫士姓名是区分大小写的英文字母字符串。

所有日期时间均使用格式 YYYY-MM-DD hh:mm，并且都位于 2009-01-01 00:00 到 2009-12-31 23:59 之间。

输出格式

输出一个实数，表示在 $[T_1,T_2)$ 内当前值班表合法的时间比例。

当绝对误差或相对误差不超过 $10^{-6}$ 时视为正确。

样例

样例输入

2 1 2
2009-12-07 09:00 2009-12-07 22:00
2009-12-07 08:00 Vasya
2009-12-07 14:00 Vanya
2009-12-07 15:00 2009-12-07 16:00 2009-12-07 20:00 Vasya

样例输出

0.53846153846153844

样例说明

初始安排中，Vasya 在 09:00 到 14:00 值班，全部属于正常工作时间；Vanya 在 14:00 到 22:00 值班，其中 18:00 到 22:00 的 4 小时属于非工作时间，超过限制 2 小时，因此初始值班表不合法。

15:00 修改生效后，16:00 到 20:00 改由 Vasya 值班。此时 Vasya 和 Vanya 各承担 2 小时非工作时间，值班表合法。因此在 13 小时的观察区间中，有 7 小时处于合法状态，答案为 $7/13$。