oj.uz

Submission #1082887

# Submission time Handle Problem Language Result Execution time Memory
1082887 2024-09-02T03:51:41 Z _callmelucian Measures (CEOI22_measures) C++17
59 / 100
 1500 ms 33240 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 732 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 628 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 600 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 732 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 1 ms 628 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 138 ms 29788 KB Output is correct
10 Correct 135 ms 29664 KB Output is correct
11 Correct 127 ms 29740 KB Output is correct
12 Correct 142 ms 29792 KB Output is correct
13 Correct 103 ms 26088 KB Output is correct
14 Correct 126 ms 29672 KB Output is correct
15 Correct 133 ms 25944 KB Output is correct
16 Correct 127 ms 29696 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 31168 KB Output is correct
2 Correct 224 ms 33112 KB Output is correct
3 Correct 221 ms 33060 KB Output is correct
4 Correct 225 ms 30852 KB Output is correct
5 Correct 227 ms 32212 KB Output is correct
6 Correct 220 ms 31192 KB Output is correct
7 Correct 216 ms 32332 KB Output is correct
8 Correct 248 ms 30964 KB Output is correct
9 Correct 219 ms 30936 KB Output is correct
10 Correct 238 ms 33240 KB Output is correct
11 Correct 223 ms 31700 KB Output is correct
12 Correct 238 ms 32764 KB Output is correct
13 Correct 226 ms 31064 KB Output is correct
14 Correct 234 ms 32980 KB Output is correct
15 Correct 226 ms 32724 KB Output is correct
16 Correct 216 ms 30508 KB Output is correct
17 Correct 227 ms 32176 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 31168 KB Output is correct
2 Correct 224 ms 33112 KB Output is correct
3 Correct 221 ms 33060 KB Output is correct
4 Correct 225 ms 30852 KB Output is correct
5 Correct 227 ms 32212 KB Output is correct
6 Correct 220 ms 31192 KB Output is correct
7 Correct 216 ms 32332 KB Output is correct
8 Correct 248 ms 30964 KB Output is correct
9 Correct 219 ms 30936 KB Output is correct
10 Correct 238 ms 33240 KB Output is correct
11 Correct 223 ms 31700 KB Output is correct
12 Correct 238 ms 32764 KB Output is correct
13 Correct 226 ms 31064 KB Output is correct
14 Correct 234 ms 32980 KB Output is correct
15 Correct 226 ms 32724 KB Output is correct
16 Correct 216 ms 30508 KB Output is correct
17 Correct 227 ms 32176 KB Output is correct
18 Correct 487 ms 31328 KB Output is correct
19 Correct 618 ms 32976 KB Output is correct
20 Correct 243 ms 33104 KB Output is correct
21 Correct 360 ms 31188 KB Output is correct
22 Execution timed out 1533 ms 29664 KB Time limit exceeded
23 Halted 0 ms 0 KB -