Submission #975596

#	Time	Username	Problem	Language	Result	Execution time	Memory
975596		rembocoder	Measures (CEOI22_measures)	C++17	24 / 100	194 ms	24252 KiB

Main

#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_x, max_x;
vector<int> seg_l, seg_r;
set<pair<pair<int, int>, int>> segs;
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});
    dsu_p[a] = b;
    dsu_sz[b] += dsu_sz[a];
    min_x[b] = min(min_x[b], min_x[a]);
    max_x[b] = max(max_x[b], max_x[a]);
    int mid = (min_x[b] + max_x[b]) / 2;
    int half_len = (dsu_sz[b] - 1) * d / 2;
    seg_l[b] = mid - half_len;
    seg_r[b] = mid + half_len;
    segs.insert({{seg_l[b], seg_r[b]}, b});
    ans = max(ans, min_x[b] - seg_l[b]);
    ans = max(ans, seg_r[b] - max_x[b]);
    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_x.resize(n + m);
    max_x.resize(n + m);
    seg_l.resize(n + m);
    seg_r.resize(n + m);
    vector<int> x(n + m);
    for (int i = 0; i < n + m; i++) {
        cin >> x[i];
        x[i] *= 2;
        min_x[i] = max_x[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: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41