oj.uz

Submission #750760

# Submission time Handle Problem Language Result Execution time Memory
750760 2023-05-30T09:02:21 Z drdilyor Measures (CEOI22_measures) C++17
0 / 100
 1500 ms 1060 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Correct 2 ms 296 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 312 KB Output is correct
7 Incorrect 3 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Correct 2 ms 296 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 312 KB Output is correct
7 Incorrect 3 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1546 ms 1060 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1546 ms 1060 KB Time limit exceeded
2 Halted 0 ms 0 KB -