oj.uz

Submission #975617

# Submission time Handle Problem Language Result Execution time Memory
975617 2024-05-05T14:58:20 Z rembocoder Measures (CEOI22_measures) C++17
35 / 100
 204 ms 24704 KB 
#include <bits/stdc++.h>

using namespace std;

#define int int64_t

const int inf = 2e18;

//const int mod = 1e9 + 7;

vector<int> dsu_p, dsu_sz;
vector<int> min_y, max_y;
vector<int> seg_l, seg_r;
set<pair<pair<int, int>, int>> segs;
vector<int> x;
int d;
int ans = 0;

int get_root(int v) {
    if (dsu_p[v] == -1) {
        return v;
    }
    return dsu_p[v] = get_root(dsu_p[v]);
}

void unite(int a, int b);

void check_seg(int v) {
    v = get_root(v);
    auto it = segs.find({{seg_l[v], seg_r[v]}, v});
    vector<int> to_unite;
    it++;
    if (it != segs.end()) {
        if (it->first.first - seg_r[v] <= d) {
            to_unite.push_back(it->second);
        }
    }
    it--;
    if (it != segs.begin()) {
        it--;
        if (seg_l[v] - it->first.second <= d) {
            to_unite.push_back(it->second);
        }
        it++;
    }
    for (int u: to_unite) {
        unite(v, u);
    }
}

void unite(int a, int b) {
    a = get_root(a);
    b = get_root(b);
    if (a == b) {
        return;
    }

    if (dsu_sz[a] > dsu_sz[b]) {
        swap(a, b);
    }

    segs.erase({{seg_l[a], seg_r[a]}, a});
    segs.erase({{seg_l[b], seg_r[b]}, b});

    int l = a, r = b;
    if (x[r] < x[l]) {
        swap(l, r);
    }
    min_y[r] -= d * dsu_sz[l];
    max_y[r] -= d * dsu_sz[l];

    dsu_p[a] = b;
    dsu_sz[b] += dsu_sz[a];

    min_y[b] = min(min_y[b], min_y[a]);
    max_y[b] = max(max_y[b], max_y[a]);

    int y = (min_y[b] + max_y[b]) / 2;

    seg_l[b] = y;
    seg_r[b] = y + (dsu_sz[b] - 1) * d;

    segs.insert({{seg_l[b], seg_r[b]}, b});

    ans = max(ans, (max_y[b] - min_y[b]) / 2);

    check_seg(b);
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m >> d;
    d *= 2;
    dsu_p.resize(n + m, -1);
    dsu_sz.resize(n + m, 1);
    min_y.resize(n + m);
    max_y.resize(n + m);
    seg_l.resize(n + m);
    seg_r.resize(n + m);
    x.resize(n + m);
    for (int i = 0; i < n + m; i++) {
        cin >> x[i];
        x[i] *= 2;
        min_y[i] = max_y[i] = x[i];
        seg_l[i] = seg_r[i] = x[i];
    }
    for (int i = 0; i < n + m; i++) {
        segs.insert({{seg_l[i], seg_r[i]}, i});
        check_seg(i);
        if (i >= n) {
            cout << ans / 2;
            if (ans % 2) {
                cout << ".5";
            }
            cout << ' ';
        }
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 668 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 668 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 21596 KB Output is correct
2 Correct 66 ms 14164 KB Output is correct
3 Correct 76 ms 14192 KB Output is correct
4 Correct 122 ms 24148 KB Output is correct
5 Correct 64 ms 13396 KB Output is correct
6 Correct 127 ms 22480 KB Output is correct
7 Correct 64 ms 13480 KB Output is correct
8 Correct 103 ms 24408 KB Output is correct
9 Correct 117 ms 24704 KB Output is correct
10 Correct 67 ms 14476 KB Output is correct
11 Correct 112 ms 24328 KB Output is correct
12 Correct 65 ms 13908 KB Output is correct
13 Correct 107 ms 24628 KB Output is correct
14 Correct 65 ms 14044 KB Output is correct
15 Correct 76 ms 13948 KB Output is correct
16 Correct 65 ms 12112 KB Output is correct
17 Correct 63 ms 13412 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 21596 KB Output is correct
2 Correct 66 ms 14164 KB Output is correct
3 Correct 76 ms 14192 KB Output is correct
4 Correct 122 ms 24148 KB Output is correct
5 Correct 64 ms 13396 KB Output is correct
6 Correct 127 ms 22480 KB Output is correct
7 Correct 64 ms 13480 KB Output is correct
8 Correct 103 ms 24408 KB Output is correct
9 Correct 117 ms 24704 KB Output is correct
10 Correct 67 ms 14476 KB Output is correct
11 Correct 112 ms 24328 KB Output is correct
12 Correct 65 ms 13908 KB Output is correct
13 Correct 107 ms 24628 KB Output is correct
14 Correct 65 ms 14044 KB Output is correct
15 Correct 76 ms 13948 KB Output is correct
16 Correct 65 ms 12112 KB Output is correct
17 Correct 63 ms 13412 KB Output is correct
18 Incorrect 204 ms 21836 KB Output isn't correct
19 Halted 0 ms 0 KB -