Submission #841659

#	Time	Username	Problem	Language	Result	Execution time	Memory
841659		Ormlis	Closing Time (IOI23_closing)	C++17	100 / 100	508 ms	47864 KiB

closing

#include "bits/stdc++.h"
#include "closing.h"

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define ar array

using namespace std;

typedef long long ll;

using pi = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;

const ll INF = 4e18;


struct fenwick {
    vector<ll> fenw;
    int n;

    void build(int _n) {
        n = _n;
        fenw.resize(n);
    }

    void upd(int i, ll x) {
        for (; i < n; i = i | (i + 1)) fenw[i] += x;
    }

    ll get(int i) {
        ll r = 0;
        for(; i >= 0; i = (i & (i + 1)) - 1) r += fenw[i];
        return r;
    }

    ll get(int l, int r) {
        if (l >= r) return 0;
        return get(r - 1) - get(l - 1);
    }

    int lower_bound(ll x) {
        int r = -1;
        for(int j = 20; j >= 0; --j) {
            int r2 = r + (int)(1 << j);
            if (r2 < n && fenw[r2] < x) {
                r = r2;
                x -= fenw[r2];
            }
        }
        return r + 1;
    }

    int upper_bound(ll x) {
        return lower_bound(x + 1);
    }
};

int lower_bound2(ll x, fenwick &f1, fenwick &f2) {
    assert(f1.n == f2.n);
    int r = -1;
    for(int j = 20; j >= 0; --j) {
        int r2 = r + (int)(1 << j);
        if (r2 < f1.n && f1.fenw[r2] + f2.fenw[r2] < x) {
            r = r2;
            x -= f1.fenw[r2] + f2.fenw[r2];
        }
    }
    return r + 1;
}


int upper_bound2(ll x, fenwick &f1, fenwick &f2) {
    return lower_bound2(x + 1, f1, f2);
}

pair<vl, vi> BuildC(int n, int x, vector<vpi> g) {
    vector<ll> c(n, INF);
    vector<int> p(n, -1);
    c[x] = 0;
    queue<int> q;
    q.push(x);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto [u, w]: g[v]) {
            if (c[u] > w + c[v]) {
                c[u] = w + c[v];
                p[u] = v;
                q.push(u);
            }
        }
    }
    return {c, p};
}

int max_score(int n, int x, int y, ll k, vi U, vi V, vi W) {
    k *= 2;
    int ans = 2;
    vector<vpi> g(n);
    rep(i, U.size()) {
        int u = U[i];
        int v = V[i];
        int w = W[i];
        w *= 2;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    auto [cx, px] = BuildC(n, x, g);
    auto [cy, py] = BuildC(n, y, g);
    {
        auto sx = cx, sy = cy;
        sort(all(sx));
        sort(all(sy));
        ll sum = accumulate(all(sy), 0ll);
        int j = n;
        for (int i = 0; i <= n; ++i) {
            if (i) sum += sx[i - 1];
            while (j > 0 && sum > k) {
                j--;
                sum -= sy[j];
            }
            if (sum > k) break;
            ans = max(ans, i + j);
        }
    }
    vector<int> mids;

    {
        ll mx = INF;
        rep(i, n) {
            ll val = max(cx[i], cy[i]);
            if (val < mx) {
                mids.clear();
                mx = val;
            }
            if (val == mx) mids.emplace_back(i);
        }
    }
    for (auto mid: mids) {
        vector<int> state(n);
        ll use = max(cx[mid], cy[mid]);
        state[mid] = 2;
        for (int vx = px[mid]; vx != -1; vx = px[vx]) {
            state[vx] = 1;
            use += cx[vx];
        }
        for (int vy = py[mid]; vy != -1; vy = py[vy]) {
            state[vy] = 1;
            use += cy[vy];
        }
        if (use > k) continue;
        int score_default = accumulate(all(state), 0);
        ans = max(ans, score_default);
        vector<ll> xx;
        xx.push_back(-INF);
        xx.push_back(INF);
        vector<ll> diff(n), mx(n), mn(n);
        rep(i, n) {
            diff[i] = abs(cx[i] - cy[i]);
            xx.push_back(diff[i]);
            mn[i] = min(cx[i], cy[i]);
            mx[i] = max(cx[i], cy[i]);
            xx.push_back(mx[i] / 2);
        }
        sort(all(xx));
        xx.resize(unique(all(xx)) - xx.begin());
        auto GetInd = [&](ll x) {
            int i = lower_bound(all(xx), x) - xx.begin();
            return i;
        };
        int sz = xx.size();
        fenwick st1, st2, ct1, ct2;
        st1.build(sz);
        st2.build(sz);
        ct1.build(sz);
        ct2.build(sz);
        vi ord2;
        vi ord1;
        rep(i, n) {
            if (state[i] == 2) continue;
            if (state[i] == 1) {
                st1.upd(GetInd(diff[i]), diff[i]);
                ct1.upd(GetInd(diff[i]), 1);
                continue;
            }
            ord2.push_back(i);
            ord1.push_back(i);
        }
        sort(all(ord1),
             [&](const int &i, const int &j) { return mn[i] < mn[j]; });
        sort(all(ord2),
             [&](const int &i, const int &j) { return diff[i] < diff[j]; });
        vector<bool> ok(n);
        auto FindNext = [&](int l) {
            return ct1.lower_bound(ct1.get(l - 1) + 1);
        };
        auto FindLast = [&](int l) {
            int pos = ct1.lower_bound(ct1.get(l));
            if (pos == 0) return -1;
            return pos;
        };

        auto FindNext2 = [&](int l) {
            return ct2.lower_bound(ct2.get(l - 1) + 1);
        };
        auto Check = [&]() {
            if (use > k) return;
            int l = -1;
            int r = upper_bound2(k - use, st1, st2);
            l = r - 1;
            int SCORE = score_default + ct1.get(0, r) + ct2.get(0, r) * 2;
            if (r == sz) {
                ans = max(ans, SCORE);
                return;
            }
            ll HAVE = k - use - st1.get(0, r) - st2.get(0, r);
            int CNT1 = ct1.get(r, r + 1);
            int CNT2 = ct2.get(r, r + 1);
            int nxt = FindNext(r + 1);
            int last = FindLast(l);
            int to2 = CNT2 ? r : FindNext2(r);
            {
                int CNT22 = ct2.get(to2, to2 + 1);
                if (last != -1 && to2 != sz) {
                    int score = SCORE;
                    int cnt2 = CNT22;
                    ll have = HAVE;
                    score--;
                    have += xx[last];
                    ll t2 = min(1ll * cnt2, have / (2 * xx[to2]));
                    score += t2 * 2;
                    ans = max(ans, score);
                }
                if (to2 != sz) {
                    ll have = HAVE;
                    int cnt2 = CNT22;
                    int score = SCORE;
                    ll t2 = min(1ll * cnt2, have / (2 * xx[to2]));
                    score += t2 * 2;
                    ans = max(ans, score);
                }
            }
            {
                ll have = HAVE;
                int cnt2 = CNT2;
                int score = SCORE;
                int cnt1 = CNT1;
                if (cnt2) {
                    ll t2 = min(1ll * cnt2, have / (2 * xx[r]));
                    cnt2 -= t2;
                    have -= t2 * xx[r] * 2;
                    score += t2 * 2;
                }

                if (cnt1) {
                    ll t1 = min(1ll * cnt1, have / xx[r]);
                    cnt1 -= t1;
                    have -= t1 * xx[r];
                    score += t1;
                }

                if (nxt != sz && xx[nxt] <= have) score++;
                ans = max(ans, score);
            }
        };
        int uk2 = 0;
        auto Check2 = [&](ll value) {
            while (uk2 < ord2.size() && diff[ord2[uk2]] <= value) {
                int i = ord2[uk2++];
                if (state[i] == 0) {
                    ok[i] = true;
                    st2.upd(GetInd(mx[i] / 2), mx[i]);
                    ct2.upd(GetInd(mx[i] / 2), 1);
                }
            }
            Check();
        };
        for (auto &i: ord1) {
            Check2(mn[i] - 1);
            state[i] = 1;
            use += mn[i];
            if (use > k) break;
            score_default++;
            if (ok[i]) {
                st2.upd(GetInd(mx[i] / 2), -mx[i]);
                ct2.upd(GetInd(mx[i] / 2), -1);
            }
            st1.upd(GetInd(diff[i]), diff[i]);
            ct1.upd(GetInd(diff[i]), 1);
            Check();
        }
        Check2(INF);
    }
    return ans;
}

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, ll, vi, vi, vi)':
closing.cpp:4:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i, n) for(int i = 0; i < (n); ++i)
      |                                    ^
closing.cpp:104:5: note: in expansion of macro 'rep'
  104 |     rep(i, U.size()) {
      |     ^~~
closing.cpp: In lambda function:
closing.cpp:272:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  272 |             while (uk2 < ord2.size() && diff[ord2[uk2]] <= value) {
      |                    ~~~~^~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 17 / 17