oj.uz

Submission #1082877

# Submission time Handle Problem Language Result Execution time Memory
1082877 2024-09-02T03:20:50 Z _callmelucian Measures (CEOI22_measures) C++14
59 / 100
 1500 ms 33244 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));
    }
};

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();
    };

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

    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.query(tmp, 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.query(prv[tmp], 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.query(0, n + m - 1, 1, 0, n + m - 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 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 736 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 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 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 736 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 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 132 ms 29660 KB Output is correct
10 Correct 130 ms 29756 KB Output is correct
11 Correct 130 ms 29712 KB Output is correct
12 Correct 149 ms 29668 KB Output is correct
13 Correct 99 ms 26204 KB Output is correct
14 Correct 119 ms 29664 KB Output is correct
15 Correct 108 ms 25836 KB Output is correct
16 Correct 120 ms 29792 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 31188 KB Output is correct
2 Correct 221 ms 33240 KB Output is correct
3 Correct 229 ms 33244 KB Output is correct
4 Correct 241 ms 30936 KB Output is correct
5 Correct 236 ms 32112 KB Output is correct
6 Correct 216 ms 31192 KB Output is correct
7 Correct 214 ms 32232 KB Output is correct
8 Correct 223 ms 31064 KB Output is correct
9 Correct 217 ms 30936 KB Output is correct
10 Correct 217 ms 33240 KB Output is correct
11 Correct 212 ms 31704 KB Output is correct
12 Correct 249 ms 32600 KB Output is correct
13 Correct 216 ms 30968 KB Output is correct
14 Correct 218 ms 32984 KB Output is correct
15 Correct 224 ms 32724 KB Output is correct
16 Correct 218 ms 30424 KB Output is correct
17 Correct 235 ms 32212 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 31188 KB Output is correct
2 Correct 221 ms 33240 KB Output is correct
3 Correct 229 ms 33244 KB Output is correct
4 Correct 241 ms 30936 KB Output is correct
5 Correct 236 ms 32112 KB Output is correct
6 Correct 216 ms 31192 KB Output is correct
7 Correct 214 ms 32232 KB Output is correct
8 Correct 223 ms 31064 KB Output is correct
9 Correct 217 ms 30936 KB Output is correct
10 Correct 217 ms 33240 KB Output is correct
11 Correct 212 ms 31704 KB Output is correct
12 Correct 249 ms 32600 KB Output is correct
13 Correct 216 ms 30968 KB Output is correct
14 Correct 218 ms 32984 KB Output is correct
15 Correct 224 ms 32724 KB Output is correct
16 Correct 218 ms 30424 KB Output is correct
17 Correct 235 ms 32212 KB Output is correct
18 Correct 497 ms 31444 KB Output is correct
19 Correct 682 ms 33020 KB Output is correct
20 Correct 235 ms 33236 KB Output is correct
21 Correct 359 ms 31192 KB Output is correct
22 Execution timed out 1535 ms 29660 KB Time limit exceeded
23 Halted 0 ms 0 KB -