oj.uz

Submission #1082908

# Submission time Handle Problem Language Result Execution time Memory
1082908 2024-09-02T05:06:14 Z _callmelucian Measures (CEOI22_measures) C++17
59 / 100
 1500 ms 34772 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())

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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) {
        if (!lazy[k]) return;
        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 getInt() {
    int num = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        num = (num << 3) + (num << 1) + (ch - '0');
        ch = getchar();
    }
    return num;
}

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

    for (int i = 0; i < n + m; i++) {
        st[i] = 2 * getInt();
        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];
            }
        }

        /*cout << "curAns " << curAns << ": ";
        for (int j = 0; j < n + m; j++) {
            ll br = tree.query(j, j, 1, 0, n + m - 1);
            if (br < -100) cout << "inf ";
            else cout << br << " ";
        }
        cout << endl;*/

        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) {
        printf("%lld", u / 2);
        if (u % 2) printf(".5");
        printf(" ");
    }

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2764 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 55 ms 29748 KB Output is correct
10 Correct 50 ms 29664 KB Output is correct
11 Correct 45 ms 29664 KB Output is correct
12 Correct 59 ms 29916 KB Output is correct
13 Correct 29 ms 27616 KB Output is correct
14 Correct 44 ms 29644 KB Output is correct
15 Correct 32 ms 27360 KB Output is correct
16 Correct 42 ms 29744 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 32728 KB Output is correct
2 Correct 178 ms 34636 KB Output is correct
3 Correct 154 ms 34520 KB Output is correct
4 Correct 114 ms 32472 KB Output is correct
5 Correct 137 ms 33808 KB Output is correct
6 Correct 112 ms 32728 KB Output is correct
7 Correct 127 ms 33760 KB Output is correct
8 Correct 118 ms 32472 KB Output is correct
9 Correct 117 ms 32472 KB Output is correct
10 Correct 145 ms 34772 KB Output is correct
11 Correct 115 ms 33332 KB Output is correct
12 Correct 146 ms 34372 KB Output is correct
13 Correct 118 ms 32468 KB Output is correct
14 Correct 141 ms 34524 KB Output is correct
15 Correct 145 ms 34264 KB Output is correct
16 Correct 118 ms 31960 KB Output is correct
17 Correct 145 ms 33752 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 32728 KB Output is correct
2 Correct 178 ms 34636 KB Output is correct
3 Correct 154 ms 34520 KB Output is correct
4 Correct 114 ms 32472 KB Output is correct
5 Correct 137 ms 33808 KB Output is correct
6 Correct 112 ms 32728 KB Output is correct
7 Correct 127 ms 33760 KB Output is correct
8 Correct 118 ms 32472 KB Output is correct
9 Correct 117 ms 32472 KB Output is correct
10 Correct 145 ms 34772 KB Output is correct
11 Correct 115 ms 33332 KB Output is correct
12 Correct 146 ms 34372 KB Output is correct
13 Correct 118 ms 32468 KB Output is correct
14 Correct 141 ms 34524 KB Output is correct
15 Correct 145 ms 34264 KB Output is correct
16 Correct 118 ms 31960 KB Output is correct
17 Correct 145 ms 33752 KB Output is correct
18 Correct 260 ms 32988 KB Output is correct
19 Correct 386 ms 34632 KB Output is correct
20 Correct 146 ms 34564 KB Output is correct
21 Correct 169 ms 32684 KB Output is correct
22 Execution timed out 1512 ms 29652 KB Time limit exceeded
23 Halted 0 ms 0 KB -