oj.uz

Submission #806678

# Submission time Handle Problem Language Result Execution time Memory
806678 2023-08-04T08:47:26 Z alextodoran Measures (CEOI22_measures) C++17
24 / 100
 565 ms 28844 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 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 556 ms 26912 KB Output is correct
10 Correct 565 ms 26912 KB Output is correct
11 Correct 25 ms 1868 KB Output is correct
12 Correct 413 ms 26912 KB Output is correct
13 Correct 152 ms 26828 KB Output is correct
14 Correct 359 ms 26812 KB Output is correct
15 Correct 440 ms 28172 KB Output is correct
16 Correct 417 ms 28844 KB Output is correct

Subtask #3
0 / 35.0

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

Subtask #4
0 / 41.0

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