p516.ans1
======================
0.53846153846153844 

=================
p516.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int WEEK_MIN = 7 * 24 * 60;
const int WEEK_OFFSET = 3 * 24 * 60;
const int DOMAIN_END = 600000;
const int NOBODY = -2;

int n, m, t_hours;
int t1, t2;
int64_t thr;
vector<int> d_start, d_gid;
vector<int> up_a, up_b, up_e, up_gid;

unordered_map<string, int> name_id;

map<int, int> mp;
unordered_map<int64_t, int64_t> acc;
int bad_count = 0;

int get_gid(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_dt(const string& date, const string& time) {
    static const int cum[12] = {0,   31,  59,  90,  120, 151,
                                181, 212, 243, 273, 304, 334};
    int mon = stoi(date.substr(5, 2));
    int day = stoi(date.substr(8, 2));
    int hh = stoi(time.substr(0, 2));
    int mm = stoi(time.substr(3, 2));
    int doy = cum[mon - 1] + (day - 1);
    return doy * 1440 + hh * 60 + mm;
}

int read_dt() {
    string date, time;
    cin >> date >> time;
    return parse_dt(date, time);
}

int64_t count_working_days(int64_t d) {
    int64_t full_weeks = d / 7, rem = d % 7;
    int64_t c = full_weeks * 5;
    for(int j = 0; j < rem; j++) {
        if((3 + j) % 7 < 5) {
            c++;
        }
    }
    return c;
}

int64_t working_prefix(int64_t t) {
    int64_t days = t / 1440, rem = t % 1440;
    int64_t c = count_working_days(days) * 540;
    if((days + 3) % 7 < 5) {
        c += max(int64_t(0), min(rem, int64_t(1080)) - 540);
    }
    return c;
}

int64_t nonworking(int l, int r) {
    return (int64_t)(r - l) - (working_prefix(r) - working_prefix(l));
}

void add_interval(int g, int l, int r, int delta) {
    if(g < 0) {
        return;
    }

    int cl = max(l, t1), cr = min(r, t2);
    if(cl >= cr) {
        return;
    }

    int w0 = (cl + WEEK_OFFSET) / WEEK_MIN;
    int w1 = (cr - 1 + WEEK_OFFSET) / WEEK_MIN;
    for(int w = w0; w <= w1; w++) {
        int64_t ws = (int64_t)w * WEEK_MIN - WEEK_OFFSET;
        int seg_l = max((int64_t)cl, ws);
        int seg_r = min((int64_t)cr, ws + WEEK_MIN);
        if(seg_l >= seg_r) {
            continue;
        }

        int64_t key = (int64_t)g * 64 + w;
        int64_t before = acc[key];
        int64_t after = before + (int64_t)delta * nonworking(seg_l, seg_r);
        bad_count += (after > thr) - (before > thr);
        acc[key] = after;
    }
}

map<int, int>::iterator split(int pos) {
    auto it = mp.lower_bound(pos);
    if(it != mp.end() && it->first == pos) {
        return it;
    }

    --it;
    mp[pos] = it->second;
    return mp.find(pos);
}

void assign(int b, int e, int g) {
    auto it_r = split(e);
    auto it_l = split(b);
    for(auto it = it_l; it != it_r; ++it) {
        add_interval(it->second, it->first, next(it)->first, -1);
    }

    mp.erase(it_l, it_r);
    mp[b] = g;
    add_interval(g, b, e, +1);
}

void read() {
    cin >> n >> m >> t_hours;
    thr = (int64_t)t_hours * 60;
    t1 = read_dt();
    t2 = read_dt();

    d_start.resize(n);
    d_gid.resize(n);
    for(int i = 0; i < n; i++) {
        d_start[i] = read_dt();
        string name;
        cin >> name;
        d_gid[i] = get_gid(name);
    }

    up_a.resize(m);
    up_b.resize(m);
    up_e.resize(m);
    up_gid.resize(m);
    for(int i = 0; i < m; i++) {
        up_a[i] = read_dt();
        up_b[i] = read_dt();
        up_e[i] = read_dt();
        string name;
        cin >> name;
        up_gid[i] = get_gid(name);
    }
}

void solve() {
    // Pure implementation. Dates are turned into minutes since 2009-01-01
    // 00:00. The schedule evolves over wall-clock time: it starts as the
    // initial assignment and each update at time A overwrites the slot [B, E)
    // with one guardian. We must integrate the wall-clock time inside [t1, t2]
    // during which the currently-active version of the schedule is valid, i.e.
    // no guardian works more than T non-working hours in any calendar week
    // (only duty inside [t1, t2] counts).
    //
    // The current schedule is kept as an interval-assignment structure (an ODT
    // on a std::map): mp[start] = guardian, covering [start, next). For every
    // interval we add its non-working minutes within [t1, t2], split per
    // calendar week, into acc[(guardian, week)], and keep bad_count = number of
    // those pairs exceeding the limit; the schedule is valid exactly when
    // bad_count == 0. An update splits at B and E, subtracts the contributions
    // of the erased pieces, and adds the new one, so bad_count stays current in
    // amortized near-constant work per update.
    //
    // Updates arrive in non-decreasing time order, so we sweep them: the
    // version active just before applying update i holds from the previous
    // event time until A_i, and we add that wall-clock span (clipped to [t1,
    // t2]) to the valid total whenever bad_count == 0. Ties at the same A_i
    // give zero-length spans and contribute nothing. The answer is the valid
    // span divided by (t2 - t1).

    mp.clear();
    acc.clear();
    bad_count = 0;

    mp[0] = NOBODY;
    for(int i = 0; i < n; i++) {
        mp[d_start[i]] = d_gid[i];
    }
    mp[DOMAIN_END] = -1;

    for(auto it = mp.begin(); next(it) != mp.end(); ++it) {
        add_interval(it->second, it->first, next(it)->first, +1);
    }

    int64_t valid = 0;
    int prev = t1;
    for(int i = 0; i < m; i++) {
        int seg_l = max(t1, prev), seg_r = min(t2, up_a[i]);
        if(seg_r > seg_l && bad_count == 0) {
            valid += seg_r - seg_l;
        }

        if(up_a[i] >= t2) {
            prev = t2;
            break;
        }

        assign(up_b[i], up_e[i], up_gid[i]);
        prev = up_a[i];
    }

    int seg_l = max(t1, prev), seg_r = t2;
    if(seg_r > seg_l && bad_count == 0) {
        valid += seg_r - seg_l;
    }

    cout << setprecision(17) << (double)valid / (double)(t2 - t1) << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p516.in1
======================
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 

=================
statement.txt
======================
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.

=================
