Submission #862123

#	Time	Username	Problem	Language	Result	Execution time	Memory
862123		vgtcross	Measures (CEOI22_measures)	C++17	59 / 100	273 ms	6748 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

void print_ans(ll ans) {
    cout << ans/2;
    if (ans & 1) cout << ".5";
    cout << ' ';
}

void solve() {
    ll n, m, d;
    cin >> n >> m >> d;
     
    if (m <= 10) {
        d *= 2;
        vector<ll> v(n);
        for (ll &i : v) {
            cin >> i;
            i *= 2;
        }

        for (int i = 0; i < m; ++i) {
            ll u;
            cin >> u;
            v.push_back(2*u);
            sort(v.begin(), v.end());
            ll l = -1, r = 1e15;
            while (r-l > 1) {
                ll md = (l + r) / 2;
                ll pp = -1e18;
                bool g = 1;
                for (int j : v) {
                    ll pos = max(j - md, pp + d);
                    g &= pos <= j + md;
                    pp = pos;
                }
                if (g) r = md;
                else l = md;
            }
            print_ans(r);
        }
    } else {
        ll ans = 0;
        ll minv = 1e18;
        for (int i = 0; i < m; ++i) {
            ll v;
            cin >> v;
            v = d * i - v;
            minv = min(minv, v);
            ans = max(ans, v - minv);
            print_ans(ans);
        }
    }
    cout << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    solve();
}

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