oj.uz

답안 #806678

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 111 ms 6020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 111 ms 6020 KB Output isn't correct
2 Halted 0 ms 0 KB -