Submission #1082897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082897		_callmelucian	Measures (CEOI22_measures)	C++14	0 / 100	151 ms	32212 KiB

Main

#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) {
        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];
            }
        }

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

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:192:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll' {aka 'long long int'} [-Wformat=]
  192 |         printf("%d", u / 2);
      |                 ~^   ~~~~~
      |                  |     |
      |                  int   ll {aka long long int}
      |                 %lld

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41