<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

516. Schedule
Time limit per test: 1.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



From the very early days of the Kingdom one of the most honorable duties for its citizen was the duty of the Royal Guardian. The Guardians serve as personal bodyguards for the King. At any moment of time exactly one of the Guardians was assigned to perform this duty.

Recently the King have issued the new labour rules. According to these rules the five day working week (from Monday to Friday) became mandatory for all citizens. Each working day starts at 9:00 in the morning and lasts until 18:00 in the evening. Any duties in non-working hours are subject for additional reward, however it is not allowed to work more than T non-working hours during one calendar week. A week starts on 00:00 on Monday and ends on 24:00 on Sunday.

The Labour Union of Guardians has decided to check the schedule of duties of the Royal Guardians, and you were chosen to help them.

You are given the initial schedule of duties, and a list of updates to this schedule. Find the fraction of time during which the entire schedule was valid according to the labour rules. You are only interested in time interval from T1 to T2, so you ignore all the duties outside this interval.

Input
The first line of the input file contains three integers N, M and T. Here N (1 ≤ N ≤ 105) is the number of entries in the schedule, M (0 ≤ M ≤ 105) is the number of updates to the schedule, and T (0 ≤ T ≤ 123) is the number of hours that one is allowed to work during the non-working hours per week.

The second line contains two dates — T1 and T2 (It is guaranteed that T1 comes earlier than T2).

The next N lines describes the initial schedule of the Guardians. Each line consists of a date Di and the name of the Guardian that starts his duty at time Di (1 ≤ i ≤ N, it is guaranteed that Dis are in ascending order, and D1 comes no later than T1). (The name is a case-sensitive sequence of English characters.) After starting his duty at time Di the Guardian serves until the next Guardian comes to replace him.

Each of the following M lines describes the schedule of updates. Each update is described by Ai — the date when this update become active, Bi and Ei (the time slot of the update), and the Guarding name (in the same format as above). When this update becomes active, the schedule is modified in the following manner: this guardian will now serve the duties between Bi and Ei, the schedule outside this time slot is not affected (see the note below the example for more explanations). It is guaranteed that Ai comes no later than Bi, and Bi earlier than Ei. All Ais are in non-descending order. When several updates happen at the same time, you should apply them in the order they're given in the input file.

All Ti, Di, Ai, Bi and Ei in the input file are dates in format YYYY-MM-DD hh:mm. All dates are between 2009-01-01 00:00 and 2009-12-31 23:59, inclusive.

Output
Output just one number — the fraction of time from T1 to T2 during which the schedule was valid according to the labour rules. Your answer will be accepted when it's within 10-6 absolute or relative error of the correct one.

Example(s)
sample input
sample output
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 



Note
Here's what happens in the example case. We're only interested in a part of a day, from 9 in the morning to 22 in the evening. Initially, Vasya is scheduled to perform the duties from 9 in the morning to 14 in the afternoon, and Vanya is scheduled to perform the duties from 14 in the afternoon to 22 in the evening. This means Vasya works only during the working hours, and Vanya gets all the hard work of 4 non-working hours, which is more than the maximum of 2 allowed. Thus this schedule is invalid according to the labour rules.

However, at 15 in the afternoon the schedule is updated. Now, Vasya is performing the duties from 9 to 14 and from 16 to 20, and Vanya is performing the duties from 14 to 16 and from 20 to 22. This means 2 non-working hours for each of the Guardians, which is allowed under the labour rules.

So the schedule was invalid from 9 in the morning to 15 in the afternoon, and valid from 15 in the afternoon to 22 in the evening, which corresponds to the fraction of 7/13.

<|response|>
## 1. Abridged problem statement

We have a guarding schedule: at any time exactly one guardian is assigned. The schedule is piecewise constant and is described by change points.

There are updates over time. When an update becomes active at time `A`, it overwrites a schedule interval `[B, E)` with one guardian.

For the observation interval `[T1, T2)`, determine what fraction of real time the **current whole schedule** is valid.

A schedule is valid if, considering only assigned duties inside `[T1, T2)`, no guardian works more than `T` non-working hours in any calendar week.

Working time is Monday–Friday, 09:00–18:00. A week starts Monday 00:00.



## 2. Key observations

### Observation 1 — Sweep update activation times

Updates are already given in non-decreasing activation time `A`.

Between two consecutive update activation times, the schedule does not change. Therefore:

- if the current schedule is valid, the whole time segment contributes to the answer;
- otherwise it contributes nothing.

So we process updates chronologically and maintain whether the current schedule is valid.

---

### Observation 2 — Only `[T1, T2)` matters

When checking validity, duties outside `[T1, T2)` are ignored.

So whenever we add/remove an interval `[l, r)` from the schedule, we first clip it:

```text
[max(l, T1), min(r, T2))
```

If the clipped interval is empty, it contributes nothing.

---

### Observation 3 — Validity is per guardian per week

For every pair:

```text
(guardian, calendar week)
```

we maintain the number of non-working minutes assigned to that guardian in that week.

Let:

```text
limit = T * 60
```

The schedule is valid iff every stored value is at most `limit`.

Instead of checking all pairs after every update, maintain:

```text
bad_count = number of guardian/week pairs with value > limit
```

Then the current schedule is valid exactly when:

```text
bad_count == 0
```

---

### Observation 4 — Current schedule can be stored as intervals

Store the current schedule in an ordered map:

```text
start_time -> guardian
```

If we have:

```text
mp[x] = g
```

and the next key is `y`, then guardian `g` works on `[x, y)`.

To apply assignment `[B, E) = G`:

1. Ensure there is a boundary at `B`.
2. Ensure there is a boundary at `E`.
3. Remove all old intervals fully inside `[B, E)`.
4. Insert the new interval `[B, E)` assigned to `G`.

This is a standard ordered disjoint interval structure.



## 3. Full solution approach

### Date conversion

All dates are in 2009. Convert each date-time to minutes since:

```text
2009-01-01 00:00
```

Example:

```text
minute = day_of_year * 1440 + hour * 60 + minute
```

2009-01-01 was Thursday.

---

### Computing non-working minutes

Define:

```cpp
working_prefix(t)
```

as the number of working minutes in `[0, t)`.

Then:

```cpp
working_minutes(l, r) = working_prefix(r) - working_prefix(l)
nonworking(l, r) = (r - l) - working_minutes(l, r)
```

Working time is Monday–Friday from 09:00 to 18:00.

---

### Updating guardian/week counters

For an interval `[l, r)` assigned to guardian `g`:

1. Clip it to `[T1, T2)`.
2. Split the clipped interval by calendar week.
3. For each weekly segment, compute non-working minutes.
4. Add or subtract those minutes from `acc[g, week]`.
5. Update `bad_count` if the value crosses the limit.

There are only about 53 calendar weeks in 2009, so weekly splitting is effectively constant-time.

---

### Applying an update

For update:

```text
at time A: assign guardian G to [B, E)
```

we do:

```text
split at E
split at B
subtract old intervals inside [B, E)
erase old intervals
insert [B, E) -> G
add new interval contribution
```

---

### Sweeping time

Let `prev = T1`.

For each update in chronological order:

1. The current schedule is active on `[prev, A)`.
2. Intersect this with `[T1, T2)`.
3. If `bad_count == 0`, add its length to `valid`.
4. Apply the update.
5. Set `prev = A`.

After all updates, process `[prev, T2)`.

Answer:

```text
valid / (T2 - T1)
```

---

### Complexity

Let `K` be the total number of interval pieces removed or created.

The complexity is:

```text
O((N + M + K) log(N + M))
```

In this interval assignment setting, the number of stored interval boundaries is `O(N + M)`, so this is efficient enough.

Memory usage:

```text
O(N + M)
```



## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

const int DAY_MIN = 24 * 60;
const int WEEK_MIN = 7 * DAY_MIN;

// 2009-01-01 was Thursday.
// If Monday is weekday 0, then Thursday is 3.
const int WEEK_OFFSET = 3 * DAY_MIN;

// All dates are inside 2009, so this is safely after the whole domain.
const int DOMAIN_END = 600000;

// Artificial value for intervals before the first real guardian.
const int NOBODY = -2;

int N, M, T_hours;
int T1, T2;
long long limit_minutes;

unordered_map<string, int> name_id;

vector<int> init_time, init_guard;
vector<int> upd_a, upd_b, upd_e, upd_guard;

// Current schedule:
// mp[x] = guardian on interval [x, next_key)
map<int, int> mp;

// acc[(guardian, week)] = non-working minutes.
// There are fewer than 64 weeks, so encode as guardian * 64 + week.
unordered_map<long long, long long> acc;

// Number of guardian/week pairs exceeding the allowed limit.
int bad_count = 0;

int get_guard_id(const string& name) {
    auto it = name_id.find(name);
    if (it != name_id.end()) return it->second;

    int id = (int)name_id.size();
    name_id[name] = id;
    return id;
}

int parse_datetime(const string& date, const string& time) {
    static const int cum_days[12] = {
        0, 31, 59, 90, 120, 151,
        181, 212, 243, 273, 304, 334
    };

    int month = stoi(date.substr(5, 2));
    int day = stoi(date.substr(8, 2));
    int hour = stoi(time.substr(0, 2));
    int minute = stoi(time.substr(3, 2));

    int day_of_year = cum_days[month - 1] + (day - 1);
    return day_of_year * DAY_MIN + hour * 60 + minute;
}

int read_datetime() {
    string date, time;
    cin >> date >> time;
    return parse_datetime(date, time);
}

long long count_working_days(long long days) {
    long long full_weeks = days / 7;
    long long rem = days % 7;

    long long result = full_weeks * 5;

    for (int i = 0; i < rem; i++) {
        int weekday = (3 + i) % 7;
        if (weekday < 5) {
            result++;
        }
    }

    return result;
}

long long working_prefix(long long t) {
    long long days = t / DAY_MIN;
    long long inside_day = t % DAY_MIN;

    long long result = count_working_days(days) * 540;

    int weekday = (days + 3) % 7;

    // Monday-Friday.
    if (weekday < 5) {
        // Working interval is [09:00, 18:00) = [540, 1080).
        long long add = min(inside_day, 1080LL) - 540LL;
        if (add > 0) result += add;
    }

    return result;
}

long long nonworking_minutes(int l, int r) {
    long long total = r - l;
    long long working = working_prefix(r) - working_prefix(l);
    return total - working;
}

// Add or remove interval [l, r) assigned to guardian g.
// delta = +1 means add contribution.
// delta = -1 means remove contribution.
void add_interval_contribution(int g, int l, int r, int delta) {
    if (g < 0) return;

    // Only [T1, T2) matters.
    int cl = max(l, T1);
    int cr = min(r, T2);

    if (cl >= cr) return;

    // Calendar week indices.
    int w0 = (cl + WEEK_OFFSET) / WEEK_MIN;
    int w1 = (cr - 1 + WEEK_OFFSET) / WEEK_MIN;

    for (int w = w0; w <= w1; w++) {
        long long week_start = 1LL * w * WEEK_MIN - WEEK_OFFSET;
        long long week_end = week_start + WEEK_MIN;

        int seg_l = max<long long>(cl, week_start);
        int seg_r = min<long long>(cr, week_end);

        if (seg_l >= seg_r) continue;

        long long key = 1LL * g * 64 + w;

        long long before = acc[key];
        long long add = nonworking_minutes(seg_l, seg_r);
        long long after = before + delta * add;

        // Check whether this pair crosses the bad/good boundary.
        if (before > limit_minutes) bad_count--;
        if (after > limit_minutes) bad_count++;

        acc[key] = after;
    }
}

// Ensure that the ordered map has a boundary at position pos.
// Returns iterator to mp[pos].
map<int, int>::iterator split_schedule(int pos) {
    auto it = mp.lower_bound(pos);

    if (it != mp.end() && it->first == pos) {
        return it;
    }

    // The previous interval contains pos.
    --it;
    int current_guard = it->second;

    mp[pos] = current_guard;
    return mp.find(pos);
}

// Assign guardian g to interval [b, e).
void assign_interval(int b, int e, int g) {
    auto it_r = split_schedule(e);
    auto it_l = split_schedule(b);

    // Remove old interval contributions.
    for (auto it = it_l; it != it_r; ++it) {
        auto nxt = next(it);
        add_interval_contribution(it->second, it->first, nxt->first, -1);
    }

    // Erase old schedule pieces inside [b, e).
    mp.erase(it_l, it_r);

    // Insert the new assigned interval.
    mp[b] = g;

    // Add its contribution.
    add_interval_contribution(g, b, e, +1);
}

void read_input() {
    cin >> N >> M >> T_hours;

    limit_minutes = 1LL * T_hours * 60;

    T1 = read_datetime();
    T2 = read_datetime();

    init_time.resize(N);
    init_guard.resize(N);

    for (int i = 0; i < N; i++) {
        init_time[i] = read_datetime();

        string name;
        cin >> name;

        init_guard[i] = get_guard_id(name);
    }

    upd_a.resize(M);
    upd_b.resize(M);
    upd_e.resize(M);
    upd_guard.resize(M);

    for (int i = 0; i < M; i++) {
        upd_a[i] = read_datetime();
        upd_b[i] = read_datetime();
        upd_e[i] = read_datetime();

        string name;
        cin >> name;

        upd_guard[i] = get_guard_id(name);
    }
}

void solve() {
    mp.clear();
    acc.clear();
    bad_count = 0;

    // Sentinel interval before the first real entry.
    mp[0] = NOBODY;

    // Initial schedule entries.
    for (int i = 0; i < N; i++) {
        mp[init_time[i]] = init_guard[i];
    }

    // End sentinel.
    mp[DOMAIN_END] = NOBODY;

    // Build initial guardian/week counters.
    for (auto it = mp.begin(); next(it) != mp.end(); ++it) {
        auto nxt = next(it);
        add_interval_contribution(it->second, it->first, nxt->first, +1);
    }

    long long valid_time = 0;
    int prev = T1;

    for (int i = 0; i < M; i++) {
        int a = upd_a[i];

        // Current schedule is active on [prev, a).
        int seg_l = max(T1, prev);
        int seg_r = min(T2, a);

        if (seg_l < seg_r && bad_count == 0) {
            valid_time += seg_r - seg_l;
        }

        // Updates at or after T2 cannot affect the observed time.
        if (a >= T2) {
            prev = T2;
            break;
        }

        assign_interval(upd_b[i], upd_e[i], upd_guard[i]);

        prev = a;
    }

    // Final segment after the last processed update.
    int seg_l = max(T1, prev);
    int seg_r = T2;

    if (seg_l < seg_r && bad_count == 0) {
        valid_time += seg_r - seg_l;
    }

    double answer = (double)valid_time / (double)(T2 - T1);
    cout << setprecision(17) << answer << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}
```



## 5. Python implementation with detailed comments

```python
import sys

sys.setrecursionlimit(1_000_000)

DAY_MIN = 24 * 60
WEEK_MIN = 7 * DAY_MIN

# 2009-01-01 was Thursday.
# If Monday is 0, Thursday is 3.
WEEK_OFFSET = 3 * DAY_MIN

DOMAIN_END = 600000
NOBODY = -2

CUM_DAYS = [
    0, 31, 59, 90, 120, 151,
    181, 212, 243, 273, 304, 334
]


def parse_datetime(date, time):
    """Convert YYYY-MM-DD hh:mm to minutes since 2009-01-01 00:00."""
    month = int(date[5:7])
    day = int(date[8:10])
    hour = int(time[0:2])
    minute = int(time[3:5])

    day_of_year = CUM_DAYS[month - 1] + (day - 1)
    return day_of_year * DAY_MIN + hour * 60 + minute


def count_working_days(days):
    """Count Monday-Friday days among the first `days` days of 2009."""
    full_weeks = days // 7
    rem = days % 7

    result = full_weeks * 5

    for i in range(rem):
        weekday = (3 + i) % 7
        if weekday < 5:
            result += 1

    return result


def working_prefix(t):
    """Number of working minutes in [0, t)."""
    days = t // DAY_MIN
    inside_day = t % DAY_MIN

    result = count_working_days(days) * 540

    weekday = (days + 3) % 7

    # Monday-Friday.
    if weekday < 5:
        # Working interval is [09:00, 18:00) = [540, 1080).
        result += max(0, min(inside_day, 1080) - 540)

    return result


def nonworking_minutes(l, r):
    """Number of non-working minutes in [l, r)."""
    return (r - l) - (working_prefix(r) - working_prefix(l))


# --------------------------------------------------------------------
# Treap implementation for ordered map: start_time -> guardian.
# Python has no built-in ordered map, so we use a randomized-style treap.
# Priorities are deterministic hashes of keys.
# --------------------------------------------------------------------

MASK = (1 << 64) - 1


def priority_for_key(x):
    """Deterministic pseudo-random priority for treap balancing."""
    x = (x + 0x9E3779B97F4A7C15) & MASK
    x = ((x ^ (x >> 30)) * 0xBF58476D1CE4E5B9) & MASK
    x = ((x ^ (x >> 27)) * 0x94D049BB133111EB) & MASK
    return x ^ (x >> 31)


class Node:
    __slots__ = ("key", "val", "prio", "left", "right")

    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prio = priority_for_key(key)
        self.left = None
        self.right = None


def merge(a, b):
    """Merge two treaps where all keys in a are smaller than all keys in b."""
    if a is None:
        return b
    if b is None:
        return a

    if a.prio > b.prio:
        a.right = merge(a.right, b)
        return a
    else:
        b.left = merge(a, b.left)
        return b


def split(root, key):
    """
    Split treap into:
    left: keys < key
    right: keys >= key
    """
    if root is None:
        return None, None

    if root.key < key:
        a, b = split(root.right, key)
        root.right = a
        return root, b
    else:
        a, b = split(root.left, key)
        root.left = b
        return a, root


def has_key(root, key):
    """Check whether key exists in the treap."""
    while root is not None:
        if key == root.key:
            return True
        if key < root.key:
            root = root.left
        else:
            root = root.right
    return False


def predecessor_value(root, key):
    """Value at the greatest key strictly smaller than `key`."""
    result = None

    while root is not None:
        if root.key < key:
            result = root.val
            root = root.right
        else:
            root = root.left

    return result


def insert_node(root, node):
    """Insert a new node. Assumes the key is not already present."""
    left, right = split(root, node.key)
    return merge(merge(left, node), right)


def collect_inorder(root, out):
    """Collect treap entries in increasing key order."""
    if root is None:
        return

    collect_inorder(root.left, out)
    out.append((root.key, root.val))
    collect_inorder(root.right, out)


def solve():
    data = sys.stdin.read().split()
    it = iter(data)

    n = int(next(it))
    m = int(next(it))
    t_hours = int(next(it))

    limit_minutes = t_hours * 60

    t1 = parse_datetime(next(it), next(it))
    t2 = parse_datetime(next(it), next(it))

    name_id = {}

    def get_guard_id(name):
        if name not in name_id:
            name_id[name] = len(name_id)
        return name_id[name]

    initial = []

    for _ in range(n):
        d = parse_datetime(next(it), next(it))
        name = next(it)
        initial.append((d, get_guard_id(name)))

    updates = []

    for _ in range(m):
        a = parse_datetime(next(it), next(it))
        b = parse_datetime(next(it), next(it))
        e = parse_datetime(next(it), next(it))
        name = next(it)

        updates.append((a, b, e, get_guard_id(name)))

    # acc[(guardian, week)] = assigned non-working minutes.
    acc = {}

    # Use a list to allow modification inside nested functions.
    bad_count = [0]

    def add_interval_contribution(g, l, r, delta):
        """
        Add or remove contribution of interval [l, r) assigned to guardian g.
        delta = +1 for adding, -1 for removing.
        """
        if g < 0:
            return

        # Only [t1, t2) matters.
        cl = max(l, t1)
        cr = min(r, t2)

        if cl >= cr:
            return

        w0 = (cl + WEEK_OFFSET) // WEEK_MIN
        w1 = (cr - 1 + WEEK_OFFSET) // WEEK_MIN

        for w in range(w0, w1 + 1):
            week_start = w * WEEK_MIN - WEEK_OFFSET
            week_end = week_start + WEEK_MIN

            seg_l = max(cl, week_start)
            seg_r = min(cr, week_end)

            if seg_l >= seg_r:
                continue

            key = (g, w)

            before = acc.get(key, 0)
            add = nonworking_minutes(seg_l, seg_r)
            after = before + delta * add

            if before > limit_minutes:
                bad_count[0] -= 1
            if after > limit_minutes:
                bad_count[0] += 1

            if after == 0:
                acc.pop(key, None)
            else:
                acc[key] = after

    # Build initial ordered map.
    # Dictionary handles possible overwrites at the same start time.
    entries = {
        0: NOBODY,
        DOMAIN_END: NOBODY
    }

    for d, g in initial:
        entries[d] = g

    root = None

    for key in sorted(entries):
        root = merge(root, Node(key, entries[key]))

    def ensure_boundary(pos):
        """
        Ensure that there is a schedule boundary at position pos.
        Equivalent to splitting an ordered interval map at pos.
        """
        nonlocal root

        if has_key(root, pos):
            return

        val = predecessor_value(root, pos)
        root = insert_node(root, Node(pos, val))

    def assign_interval(b, e, g):
        """Assign guardian g to interval [b, e)."""
        nonlocal root

        ensure_boundary(e)
        ensure_boundary(b)

        # Cut out all boundaries in [b, e).
        left, mid_right = split(root, b)
        mid, right = split(mid_right, e)

        # Remove old contributions inside [b, e).
        old_entries = []
        collect_inorder(mid, old_entries)

        for i, (start, guard) in enumerate(old_entries):
            if i + 1 < len(old_entries):
                end = old_entries[i + 1][0]
            else:
                end = e

            add_interval_contribution(guard, start, end, -1)

        # Replace removed part by a single interval start.
        root = merge(merge(left, Node(b, g)), right)

        # Add contribution of the new interval.
        add_interval_contribution(g, b, e, +1)

    # Add initial schedule contributions.
    all_entries = []
    collect_inorder(root, all_entries)

    for i in range(len(all_entries) - 1):
        start, guard = all_entries[i]
        end = all_entries[i + 1][0]
        add_interval_contribution(guard, start, end, +1)

    valid_time = 0
    prev = t1

    # Sweep update activation times.
    for a, b, e, g in updates:
        seg_l = max(t1, prev)
        seg_r = min(t2, a)

        if seg_l < seg_r and bad_count[0] == 0:
            valid_time += seg_r - seg_l

        if a >= t2:
            prev = t2
            break

        assign_interval(b, e, g)
        prev = a

    # Final segment after the last update.
    seg_l = max(t1, prev)
    seg_r = t2

    if seg_l < seg_r and bad_count[0] == 0:
        valid_time += seg_r - seg_l

    answer = valid_time / (t2 - t1)
    print("{:.17f}".format(answer))


if __name__ == "__main__":
    solve()
```