제출 #750760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
750760		drdilyor	Measures (CEOI22_measures)	C++17	0 / 100	1546 ms	1060 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9;
const ll infl = 1e18;
mt19937 rng;
template<typename T> int sz(T& x) {return x.size();}

int main() {
    ll n, m, d;
    cin >> n >> m >> d;
    d *= 2;
    vector<ll> arr(n);
    for (auto& i : arr) cin >> i, i*=2;
    while (m--) {
        arr.push_back(0);
        cin >> arr[n];
        arr[n] *= 2;
        n++;

        sort(arr.begin(), arr.end());
        vector<ll> head(n);
        vector<pair<int,int>> part;
        vector<pair<ll,ll>> seg;
        for (int i = 0; i < n; i++) {
            part.push_back({i, i});
            seg.push_back({arr[i], arr[i]});

            while (seg.size() > 1 && seg[sz(seg)-2].second+d >= seg[sz(seg)-1].first) {
                int r = part.back().second;
                part.pop_back();
                int l = part.back().first;
                part.pop_back();
                seg.pop_back();
                seg.pop_back();
                int cnt = (r - l) + 1;
                int lx = arr[l],
                    rx = arr[r];
                ll range = (cnt-1) * d;
                ll diff = range - (rx - lx);
                part.push_back({l, r});
                //cout << "l,r,lx,rx,diff=" << l <<',' << r<<','<<lx<<','<<rx<<',' <<diff << '\n';
                seg.push_back({lx - diff / 2, rx + diff / 2});
            }
        }
        ll res = 0;
        //for (auto [a, b] : part) cout << "{" << a <<',' << b << "} ";
        //cout << endl;
        //for (auto [a, b] : seg) cout << "{" << a <<',' << b << "} ";
        //cout << endl;
        for (int i = 0; i < sz(seg); i++) {
            res = max(res, abs(seg[i].first - arr[part[i].first]));
            res = max(res, abs(seg[i].second - arr[part[i].second]));
        }
        cout << res/2;
        if (res%2) cout << ".5";
        cout << ' ';
    }
    cout << '\n';
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41