Submission #205904

#	Time	Username	Problem	Language	Result	Execution time	Memory
205904		himyu	Fireworks (APIO16_fireworks)	C++17	26 / 100	10 ms	7544 KiB

fireworks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

template <class T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

vector<pli> adj[300001];
const i64 inf = numeric_limits<i64>::max() / 3;

inline i64 ab(i64 x) { return x > 0 ? x : -x; }

class slope {
   public:
    vector<i64> bp;
    i64 sac, pen;

    slope() {
        bp.clear();
        sac = 0, pen = 0;
    }

    void push(i64 x) {
        if (bp.empty()) {
            bp.emplace_back(x);
            bp.emplace_back(x);
            ++sac;
            return;
        }

        while (bp.size() > sac + 1) bp.pop_back();
        bp[sac] += x;
        bp[sac - 1] += x;
    }

    i64 get(int x) {
        if(bp.empty()) return 0;

        i64 ret = 0;
        if (x > bp[sac])
            for (int i = sac; i < bp.size(); i++) ret += max(x - bp[i], 0LL);
        if (x < bp[sac - 1])
            for (int i = sac - 1; i >= 0; i--) ret += max(bp[i] - x, 0LL);
        return ret;
    }

    void print() {
        cout<<"sac: "<<sac<<endl;
        cout<<"pen: "<<pen<<endl;
        cout<<"bp: ";
        for(auto el:bp) cout<<el<<" ";
        cout<<endl;
    }
};

slope operator+(slope &lhs, slope &rhs) {
    slope ret;
    ret.sac = lhs.sac + rhs.sac;
    ret.pen = lhs.pen + rhs.pen;
    for (auto el : lhs.bp) ret.bp.emplace_back(el);
    for (auto el : rhs.bp) ret.bp.emplace_back(el);
    sort(iterall(ret.bp));
    ret.pen += lhs.get(ret.bp[ret.sac]);
    ret.pen += rhs.get(ret.bp[ret.sac]);

    return ret;
}

slope solve(int h, int p = -1) {
    auto mer = slope();

    for (auto [t, wf] : adj[h]) {
        if (t == p) continue;
        auto chslp = solve(t, h);
        chslp.push(wf);
        mer = mer + chslp;
    }

    return mer;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    for (int i = 2; i <= N + M; i++) {
        i64 j, w;
        cin >> j >> w;

        adj[i].emplace_back(j, w);
        adj[j].emplace_back(i, w);
    }

    cout << solve(1).pen << endl;

    return 0;
}

Compilation message (stderr)

fireworks.cpp: In member function 'void slope::push(i64)':
fireworks.cpp:45:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (bp.size() > sac + 1) bp.pop_back();
                ~~~~~~~~~~^~~~~~~~~
fireworks.cpp: In member function 'i64 slope::get(int)':
fireworks.cpp:55:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = sac; i < bp.size(); i++) ret += max(x - bp[i], 0LL);
                               ~~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45