Submission #841649

#	Time	Username	Problem	Language	Result	Execution time	Memory
841649		Ormlis	Closing Time (IOI23_closing)	C++17	83 / 100	1059 ms	52464 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 SegTree {
    vector<ll> t;
    int n;

    void build(int _n) {
        n = _n;
        t.resize(n * 2);
    }

    void upd(int i, ll x) {
        for (t[i += n] += x; i > 1; i >>= 1) t[i >> 1] = t[i] + t[i ^ 1];
    }

    ll get(int l, int r) {
        ll s = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) s += t[l++];
            if (r & 1) s += t[--r];
        }
        return s;
    }
};

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();
        SegTree 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) {
            int L = l - 1;
            int R = sz;
            while (R - L > 1) {
                int mid = (L + R) / 2;
                if (ct1.get(l, mid + 1)) {
                    R = mid;
                } else {
                    L = mid;
                }
            }
            return R;
        };
        auto FindLast = [&](int l) {
            int L = -1;
            int R = l + 1;
            while (R - L > 1) {
                int mid = (L + R) / 2;
                if (ct1.get(mid, l + 1)) {
                    L = mid;
                } else {
                    R = mid;
                }
            }
            return L;
        };

        auto FindNext2 = [&](int l) {
            int L = l - 1;
            int R = sz;
            while (R - L > 1) {
                int mid = (L + R) / 2;
                if (ct2.get(l, mid + 1)) {
                    R = mid;
                } else {
                    L = mid;
                }
            }
            return R;
        };
        auto Check = [&]() {
            if (use > k) return;
            int l = -1;
            int r = sz;
            while (r - l > 1) {
                int mid = (l + r) / 2;
                ll s = st1.get(0, mid + 1) + st2.get(0, mid + 1);
                if (s + use <= k) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            int score = score_default + ct1.get(0, r) + ct2.get(0, r) * 2;
            if (r == sz) {
                ans = max(ans, score);
                return;
            }
            int cnt1 = ct1.get(r, r + 1);
            int nxt = FindNext(r + 1);
            int score2 = score;
            {
                int last = FindLast(l);
                int to2 = FindNext2(r);
                int cnt2 = ct2.get(to2, to2 + 1);
                if (last != -1 && to2 != sz) {
                    ll have = k - use - st1.get(0, r) - st2.get(0, r);
                    score--;
                    have += xx[last];

                    if (cnt2) {
                        ll t2 = min(1ll * cnt2, have / (2 * xx[r]));
                        cnt2 -= t2;
                        have -= t2 * xx[r] * 2;
                        score += t2 * 2;
                    }
                    ans = max(ans, score);
                    score = score2;
                }
                if (to2 != sz) {
                    ll have = k - use - st1.get(0, r) - st2.get(0, r);
                    if (cnt2) {
                        ll t2 = min(1ll * cnt2, have / (2 * xx[r]));
                        cnt2 -= t2;
                        have -= t2 * xx[r] * 2;
                        score += t2 * 2;
                    }
                    ans = max(ans, score);
                    score = score2;
                }
            }
            int cnt2 = ct2.get(r, r + 1);
            for (int t = 0; t <= 1; ++t) {
                score = score2;
                if (t && nxt == sz) continue;
                ll have = k - use - st1.get(0, r) - st2.get(0, r);
                if (t && xx[nxt] <= have) {
                    have -= xx[nxt];
                    score++;
                }
                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;
                }
                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:67:5: note: in expansion of macro 'rep'
   67 |     rep(i, U.size()) {
      |     ^~~
closing.cpp: In lambda function:
closing.cpp:279:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  279 |             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: 0 / 17