oj.uz

Submission #1082894

# Submission time Handle Problem Language Result Execution time Memory
1082894 2024-09-02T04:27:36 Z _callmelucian Measures (CEOI22_measures) C++14
59 / 100
 1500 ms 35032 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct IT {
    vector<ll> hi, lo, lazy;
    IT (int sz) : hi(4 * sz), lo(4 * sz), lazy(4 * sz) {}

    ll addLo (ll a, ll b) {
        return (min(a, b) == LLONG_MIN || max(a, b) == LLONG_MAX ? LLONG_MAX : a + b);
    }

    ll addHi (ll a, ll b) {
        return (min(a, b) == LLONG_MIN || max(a, b) == LLONG_MAX ? LLONG_MIN : a + b);
    }

    ll getHi (int k) { return addHi(hi[k], lazy[k]); }

    ll getLo (int k) { return addLo(lo[k], lazy[k]); }

    void refine (int k) {
        hi[k] = max(getHi(2 * k), getHi(2 * k + 1));
        lo[k] = min(getLo(2 * k), getLo(2 * k + 1));
    }

    void pushDown (int k) {
        lazy[2 * k] = addHi(lazy[2 * k], lazy[k]), lazy[2 * k + 1] = addHi(lazy[2 * k + 1], lazy[k]);
        lazy[k] = 0, refine(k);
    }

    void update (int a, int b, ll incr, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) {
            lazy[k] = addHi(lazy[k], incr);
            return;
        }
        pushDown(k);
        int mid = (l + r) >> 1;
        update(a, b, incr, 2 * k, l, mid);
        update(a, b, incr, 2 * k + 1, mid + 1, r);
        refine(k);
    }

    ll query (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return LLONG_MIN;
        if (a <= l && r <= b) return getHi(k);
        pushDown(k);
        int mid = (l + r) >> 1;
        return max(query(a, b, 2 * k, l, mid), query(a, b, 2 * k + 1, mid + 1, r));
    }

    int walk (ll targ, int k, int l, int r) {
        if (l == r) return l;
        pushDown(k);
        int mid = (l + r) >> 1;
        if (getLo(2 * k) < targ) return walk(targ, 2 * k, l, mid);
        return walk(targ, 2 * k + 1, mid + 1, r);
    }

    int findID (int a, int b, ll targ, int k, int l, int r) {
        if (b < l || r < a) return INT_MAX;
        if (a <= l && r <= b)
            return (getLo(k) < targ ? walk(targ, k, l, r) : INT_MAX);
        pushDown(k);
        int mid = (l + r) >> 1;
        int cur = findID(a, b, targ, 2 * k, l, mid);
        return (cur < INT_MAX ? cur : findID(a, b, targ, 2 * k + 1, mid + 1, r));
    }

    ll access (int pos, int k, int l, int r) {
        if (l == r) return getLo(k);
        int mid = (l + r) >> 1;
        if (pos <= mid)
            return addLo(lazy[k], access(pos, 2 * k, l, mid));
        return addLo(lazy[k], access(pos, 2 * k + 1, mid + 1, r));
    }

    void build (vector<ll> &a, int k, int l, int r) {
        if (l == r) {
            hi[k] = lo[k] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(a, 2 * k, l, mid);
        build(a, 2 * k + 1, mid + 1, r);
        refine(k);
    }
};

const int mn = 2e5 + 50;
int st[mn], nxt[mn], prv[mn];

bool ok (vector<pl> vec, ll D, ll mov) {
    ll last = LLONG_MIN;
    for (pl it : vec) {
        ll init = it.first, cur = max(init - mov, last + D);
        if (cur > init + mov) return 0;
        last = cur;
    }
    return 1;
}

ll solve (vector<pl> vec, ll D) {
    if (ok(vec, D, 0)) return 0;
    ll ans = 0;
    for (ll msk = (1LL << 60); msk > 0; msk >>= 1)
        if (!ok(vec, D, ans | msk)) ans |= msk;
    return ans + 1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, D; cin >> n >> m >> D; D *= 2;
    vector<pl> vec(n + m);

    for (int i = 0; i < n + m; i++) {
        cin >> st[i]; st[i] *= 2;
        vec[i] = {st[i], i}, nxt[i] = i + 1, prv[i] = i - 1;
    }
    prv[n + m] = n + m - 1;
    sort(all(vec));
    ll curAns = solve(vec, D), last = LLONG_MIN;

    function<int(int)> getID = [&] (int initID) {
        return lower_bound(all(vec), make_pair((ll)st[initID], (ll)initID)) - vec.begin();
    };

    vector<ll> a(n + m);
    for (int i = 0; i < n + m; i++) {
        ll init = vec[i].first, cur = max(init - curAns, last + D);
        a[i] = cur - init, last = cur;
    }
    IT tree(n + m); tree.build(a, 1, 0, n + m - 1);

    vector<ll> ans;
    for (int i = n + m - 1; i >= n; i--) {
        ans.push_back(curAns);

        int cur = getID(i);
        tree.update(cur, cur, LLONG_MIN, 1, 0, n + m - 1);

        if (prv[cur] >= 0) nxt[prv[cur]] = nxt[cur];
        prv[nxt[cur]] = prv[cur];

        if (nxt[cur] < n + m) {
            int tmp = nxt[cur];
            while (tmp < n + m) {
                ll goCur = tree.access(tmp, 1, 0, n + m - 1), pos = vec[tmp].first + goCur;
                ll gap = goCur + curAns;

                if (prv[tmp] >= 0) {
                    ll posL = vec[prv[tmp]].first + tree.access(prv[tmp], 1, 0, n + m - 1);
                    gap = min(gap, pos - posL - D);
                }
                if (!gap) break;

                int bound = prv[min(n + m, tree.findID(tmp, n + m - 1, goCur, 1, 0, n + m - 1))];
                tree.update(tmp, bound, -gap, 1, 0, n + m - 1);
                tmp = nxt[bound];
            }
        }

        ll decrAns = min(curAns, (curAns - tree.getHi(1)) / 2LL);
        tree.update(0, n + m - 1, decrAns, 1, 0, n + m - 1);
        curAns -= decrAns;
    }

    reverse(all(ans));
    for (ll u : ans)
        cout << u / 2 << (u % 2 ? ".5 " : " ");

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 62 ms 29688 KB Output is correct
10 Correct 66 ms 29664 KB Output is correct
11 Correct 56 ms 29660 KB Output is correct
12 Correct 66 ms 29660 KB Output is correct
13 Correct 30 ms 27620 KB Output is correct
14 Correct 53 ms 29656 KB Output is correct
15 Correct 40 ms 27364 KB Output is correct
16 Correct 54 ms 29780 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 32788 KB Output is correct
2 Correct 145 ms 34776 KB Output is correct
3 Correct 152 ms 34776 KB Output is correct
4 Correct 145 ms 32468 KB Output is correct
5 Correct 148 ms 33748 KB Output is correct
6 Correct 146 ms 32836 KB Output is correct
7 Correct 157 ms 33868 KB Output is correct
8 Correct 143 ms 32468 KB Output is correct
9 Correct 150 ms 32512 KB Output is correct
10 Correct 149 ms 35032 KB Output is correct
11 Correct 142 ms 33240 KB Output is correct
12 Correct 147 ms 34396 KB Output is correct
13 Correct 150 ms 32472 KB Output is correct
14 Correct 146 ms 34520 KB Output is correct
15 Correct 151 ms 34264 KB Output is correct
16 Correct 144 ms 31960 KB Output is correct
17 Correct 149 ms 33880 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 32788 KB Output is correct
2 Correct 145 ms 34776 KB Output is correct
3 Correct 152 ms 34776 KB Output is correct
4 Correct 145 ms 32468 KB Output is correct
5 Correct 148 ms 33748 KB Output is correct
6 Correct 146 ms 32836 KB Output is correct
7 Correct 157 ms 33868 KB Output is correct
8 Correct 143 ms 32468 KB Output is correct
9 Correct 150 ms 32512 KB Output is correct
10 Correct 149 ms 35032 KB Output is correct
11 Correct 142 ms 33240 KB Output is correct
12 Correct 147 ms 34396 KB Output is correct
13 Correct 150 ms 32472 KB Output is correct
14 Correct 146 ms 34520 KB Output is correct
15 Correct 151 ms 34264 KB Output is correct
16 Correct 144 ms 31960 KB Output is correct
17 Correct 149 ms 33880 KB Output is correct
18 Correct 285 ms 32928 KB Output is correct
19 Correct 444 ms 34544 KB Output is correct
20 Correct 148 ms 34772 KB Output is correct
21 Correct 214 ms 32752 KB Output is correct
22 Execution timed out 1573 ms 29668 KB Time limit exceeded
23 Halted 0 ms 0 KB -