Submission #389589

#	Time	Username	Problem	Language	Result	Execution time	Memory
389589		solaimanope	Fireworks (APIO16_fireworks)	C++17	100 / 100	315 ms	76416 KiB

fireworks

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;


/**
 * @brief Slope-Trick
 * @see https://maspypy.com/slope-trick-1-%E8%A7%A3%E8%AA%AC%E7%B7%A8
 */
template< typename T >
struct SlopeTrick {
    T INF = numeric_limits< T >::max() / 3;

    T min_f;
    priority_queue< T, vector< T >, less<> > L;
    priority_queue< T, vector< T >, greater<> > R;
    T add_l, add_r;

//private:
    void push_R(const T &a) {
        R.push(a - add_r);
    }

    T top_R() const {
        return R.top() + add_r;
    }

    T pop_R() {
        T val = top_R();
        R.pop();
        return val;
    }

    void push_L(const T &a) {
        L.push(a - add_l);
    }

    T top_L() const {
        return L.top() + add_l;
    }

    T pop_L() {
        T val = top_L();
        L.pop();
        return val;
    }

public:
    SlopeTrick() : min_f(0), add_l(0), add_r(0) {
        L.push(-INF);
        R.push(INF);
    }

    int size() {
        return int(L.size()) + int(R.size()) - 2;
    }

    struct Query {
        T lx, rx, min_f;
    };

    // return min f(x)
    Query query() const {
        return (Query) {top_L(), top_R(), min_f};
    }

    // f(x) += a
    void add_all(const T &a) {
        min_f += a;
    }


    /// has room for improvement
    // add \_
    // f(x) += max(a - x, 0)
    void add_a_minus_x(const T &a) {
        min_f += max(T(0), a - top_R());
        push_R(a);
        push_L(pop_R());
    }

    // add _/
    // f(x) += max(x - a, 0)
    void add_x_minus_a(const T &a) {
        min_f += max(T(0), top_L() - a);
        push_L(a);
        push_R(pop_L());
    }

    // add \/
    // f(x) += abs(x - a)
//    void add_abs(const T &a) {
//        add_a_minus_x(a);
//        add_x_minus_a(a);
//    }

    void add_abs(const T &a) {
        if (a < top_L()) {
            min_f += top_L() - a;
            push_L(a);
            push_L(a);
            push_R(pop_L());
        } else if (top_R() < a) {
            min_f += a - top_R();
            push_R(a);
            push_R(a);
            push_L(pop_R());
        } else {
            push_L(a);
            push_R(a);
        }
    }

    // \/ -> \_
    // f_{new} (x) = min f(y) (y <= x)
    void clear_right() {
        while(R.size() >= 2) R.pop();
    }

    // \/ -> _/
    // f_{new} (x) = min f(y) (y >= x)
    void clear_left() {
        while(L.size() >= 2) L.pop();
    }

    // \/. -> .\/
    // f_{new} (x) = f(x - a)
    void shift(const T &a) {
        add_l += a;
        add_r += a;
    }

    ///This object is no more usable after this function
    T get(const T &x) {
        T ret = min_f;

        if (!L.empty() && x < top_L()) {
            while(!L.empty()) {
                ret += max(T(0), pop_L() - x);
            }
        }
        if (!R.empty() && top_R() < x) {
            while(!R.empty()) {
                ret += max(T(0), x - pop_R());
            }
        }
        return ret;
    }
};

void print(SlopeTrick<LL>t) {
    cout << "R:";
    while (t.R.size() >= 2) cout << " " << t.pop_R();
    cout << endl;
    cout << "min_f " << t.min_f << endl;
    cout << "L:";
    while (t.L.size() >= 2) cout << " " << t.pop_L();
    cout << endl;
}

void SmallToLarge(SlopeTrick<LL> &from, SlopeTrick<LL> &to) {
    if (from.size() > to.size()) swap(from, to);
    while (from.L.size() >= 2) {
        to.add_a_minus_x(from.pop_L());
    }
    while (from.R.size() >= 2) {
        to.add_x_minus_a(from.pop_R());
    }
    to.min_f += from.min_f;
}


const int MAXN = 3e5+7;
int P[MAXN], C[MAXN];
vector< int >child[MAXN];
SlopeTrick<LL> trick[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 2; i <= n+m; i++) {
        cin >> P[i] >> C[i];
        child[P[i]].push_back(i);
    }

    for (int i = n+1; i <= n+m; i++) {
        trick[i].add_abs(C[i]);
    }

    for (int i = n; i > 0; i--) {
        for (int c : child[i]) {
//            cout << "from " << c << endl;
//            print(trick[c]);
            SmallToLarge(trick[c], trick[i]);
//            cout << i << " now " << endl;
//            print(trick[i]);
//            cout << endl;
        }
        { ///clearing all slopes greater than 1
            LL save = trick[i].top_R();
            trick[i].clear_right();
            trick[i].push_R(save);
        }
//        cout << i << " -> " << trick[i].min_f << "\n";
        if (i > 1) {
            trick[i].push_L(trick[i].pop_L()+C[i]);
            trick[i].push_R(trick[i].pop_R()+C[i]);
        }
//        cout << "after min_conv" << endl;
//        print(trick[i]);
//        cout << endl;
    }


    cout << trick[1].min_f << "\n";


    return 0;
}

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