Submission #805455

#	Time	Username	Problem	Language	Result	Execution time	Memory
805455		alextodoran	Measures (CEOI22_measures)	C++17	24 / 100	523 ms	29056 KiB

Main

/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 200000;
const int M_MAX = 200000;

int N, M; ll D;
ll A[N_MAX + 2];

multiset <pair <ll, ll>> diffs;
multiset <tuple <ll, ll, int>> groups;
ll t;

void find_t () {
    while (diffs.empty() == false && diffs.begin()->first - t * 2 < D) {
        multiset <tuple <ll, ll, int>> :: iterator itr
            = prev(groups.upper_bound(make_tuple(diffs.begin()->second, LLONG_MAX, 0)));
        multiset <tuple <ll, ll, int>> :: iterator itl = prev(itr);
        ll l1, r1; int cnt1; tie(l1, r1, cnt1) = *itl;
        ll l2, r2; int cnt2; tie(l2, r2, cnt2) = *itr;
        ll l = l1, r = r2; int cnt = cnt1 + cnt2;
        t = max(t, ((cnt - 1) * D - (r - l)) / 2);
        groups.erase(itl); groups.erase(itr); groups.insert(make_tuple(l, r, cnt));
        diffs.erase(diffs.begin());
    }
}

void update (ll x) {
    if (groups.empty() == true) {
        groups.insert(make_tuple(x, x, 1));
        return;
    }
    multiset <tuple <ll, ll, int>> :: iterator it
        = groups.upper_bound(make_tuple(x, LLONG_MAX, 0));
    if (it == groups.begin()) {
        ll y = get <0> (*it);
        diffs.insert(make_pair(y - x, y));
        groups.insert(make_tuple(x, x, 1));
        return;
    }
    it--;
    ll l, r; int cnt; tie(l, r, cnt) = *it;
    if (r < x) {
        diffs.insert(make_pair(x - r, x));
        if (next(it) != groups.end()) {
            ll y = get <0> (*next(it));
            diffs.insert(make_pair(y - x, y));
            diffs.erase(diffs.find(make_pair(y - r, y)));
        }
        groups.insert(make_tuple(x, x, 1));
    } else {
        ll l, r; int cnt; tie(l, r, cnt) = *it; cnt++;
        groups.erase(it);
        groups.insert(make_tuple(l, r, cnt));
        t = max(t, ((cnt - 1) * D - (r - l)) / 2);
    }
}
int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M >> D; D *= 2;
    for (int i = 1; i <= N; i++) {
        cin >> A[i]; A[i] *= 2;
        update(A[i]);
    }
    while (M--) {
        ll x;
        cin >> x; x *= 2;
        update(x);
        find_t();
        if (t % 2 == 0) {
            cout << t / 2 << " ";
        } else {
            cout << t / 2 << ".5 ";
        }
    }
    cout << "\n";

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41