제출 #1218072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218072		Double_Slash	Bulldozer (JOI17_bulldozer)	C++20	25 / 100	2095 ms	33408 KiB

bulldozer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;

struct Val {
    ll sum, lmx, rmx, mx;

    void operator=(int x) { lmx = rmx = mx = max(sum = x, 0ll); }

    Val operator+(const Val &o) const {
        Val ret{sum + o.sum, max(lmx, sum + o.lmx), max(rmx + o.sum, o.rmx)};
        ret.mx = max({mx, o.mx, ret.lmx, ret.rmx, rmx + o.lmx});
        return ret;
    }
};

struct St {
    int n;
    vector<Val> st;

    St(int n) : n(n), st(n << 1) {}

    void update(int i, int v) {
        for (st[i += n] = v; i >>= 1;) st[i] = st[i << 1] + st[i << 1 | 1];
    }

    ll query(int l, int r) {
        Val lagg{}, ragg{};
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) lagg = lagg + st[l++];
            if (r & 1) ragg = st[--r] + ragg;
        }
        return (lagg + ragg).mx;
    }
};

pint operator-(const pint &a, const pint &b) { return {a.first - b.first, a.second - b.second}; }

ll operator^(const pint &a, const pint &b) { return (ll) a.first * b.second - (ll) b.first * a.second; }

int main() {
    int n;
    cin >> n;
    pint p[n];
    int w[n];
    for (int i = n; i--;) cin >> p[i].first >> p[i].second >> w[i];
    int arr[n];
    iota(arr, arr + n, 0);
    sort(arr, arr + n, [&] (int i, int j) { return p[i] < p[j]; });
    St st(n);
    int idx[n];
    for (int i = n; i--;) st.update(idx[arr[i]] = i, w[arr[i]]);
    vector<pair<pint, pint>> swaps;
    for (int i = n; i--;) {
        for (int j = n; j--;) {
            pint v = p[i] - p[j];
            if (v > pint{0, 0}) swaps.emplace_back(v, pint{i, j});
        }
    }
    sort(all(swaps), [&] (auto &a, auto &b) { return (a.first ^ b.first) < 0; });
    ll ans = st.query(0, n);
    vector<pint> batch;
    vector<vector<int>> adj(n);
    vector<int> seen(n);
    for (int i = 0, t = 0; i < swaps.size(); ++i) {
        batch.push_back(swaps[i].second);
        if (i + 1 == swaps.size() or (swaps[i].first ^ swaps[i + 1].first)) {
            set<int> start;
            for (auto [a, b]: batch) {
                adj[a].clear();
                adj[b].clear();
                start.emplace(b);
            }
            for (auto [a, b]: batch) {
                adj[b].emplace_back(a);
                start.erase(a);
            }
            for (int j: start) {
                ++t;
                vector<int> order, indices;
                function<void(int)> dfs = [&] (int i) {
                    if (seen[i] == t) return;
                    seen[i] = t;
                    for (int j: adj[i]) dfs(j);
                    order.emplace_back(i);
                };
                dfs(j);
                for (int i: order) indices.emplace_back(idx[i]);
                sort(all(indices));
                for (int i = order.size(); i--;) st.update(idx[order[i]] = indices[i], w[order[i]]);
            }
            ans = max(ans, st.query(0, n));
        }
    }
    cout << ans << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20