제출 #975617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
975617		rembocoder	Measures (CEOI22_measures)	C++17	35 / 100	204 ms	24704 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_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
• Subtask 2: 0 / 14
• Subtask 3: 35 / 35
• Subtask 4: 0 / 41