oj.uz

Submission #806672

# Submission time Handle Problem Language Result Execution time Memory
806672 2023-08-04T08:43:11 Z alextodoran Measures (CEOI22_measures) C++17
10 / 100
 427 ms 26624 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];

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

void find_t () {
    while (diffs.empty() == false && diffs.begin()->first - t * 2 <= D) {
        set <tuple <ll, ll, int>> :: iterator itr
            = groups.lower_bound(make_tuple(diffs.begin()->second, 0, 0));
        set <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;
    }
    set <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(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]);
        find_t();
    }
    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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 427 ms 26624 KB Output is correct
10 Correct 24 ms 3716 KB Output is correct
11 Correct 24 ms 3788 KB Output is correct
12 Correct 24 ms 3724 KB Output is correct
13 Correct 39 ms 3276 KB Output is correct
14 Incorrect 123 ms 8844 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

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

Subtask #4
0 / 41.0

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