oj.uz

Submission #805403

# Submission time Handle Problem Language Result Execution time Memory
805403 2023-08-03T16:24:11 Z alextodoran Measures (CEOI22_measures) C++17
0 / 100
 181 ms 6048 KB 
/**
 _  _   __  _ _ _  _  _ _
 |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) {
    multiset <tuple <ll, ll, int>> :: iterator it
        = groups.upper_bound(make_tuple(x, LLONG_MAX, 0));
    if (it == groups.begin()) {
        if (groups.empty() == false) {
            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();
        cout << t / 2.0 << " ";
    }
    cout << "\n";

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Incorrect 1 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Incorrect 1 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 181 ms 6048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 181 ms 6048 KB Output isn't correct
2 Halted 0 ms 0 KB -