Submission #1005828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005828		omsincoconut	Fireworks (APIO16_fireworks)	C++17	7 / 100	2 ms	12772 KiB

fireworks

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

const ll MAXN = 3e5+5;

ll N, M, P[MAXN], C[MAXN];
vector<ll> child[MAXN];

struct MedianFinder{
    ll n = 0;
    priority_queue<ll> low, high;

    void normalize() {
        while (low.size() > (n>>1)) {
            high.push(-low.top());
            low.pop();
        }
        while (high.size() > (n>>1)) {
            low.push(-high.top());
            high.pop();
        }
    }

    void insert(ll x) {
        n++;
        if (n == 1 || x < query()) low.push(x);
        else high.push(-x);
        normalize();
    }

    void merge(MedianFinder *target, ll offset = 0) {
        while (!low.empty()) {
            target->insert(low.top() + offset);
            low.pop();
        }
        while (!high.empty()) {
            target->insert(-high.top() + offset);
            high.pop();
        }
    }

    ll query() {
        return low.top();
    }
};

MedianFinder *dt[MAXN];
ll median[MAXN];

void dfs(ll u) {
    dt[u] = new MedianFinder();
    if (u > N) {
        dt[u]->insert(0);
        median[u] = 0;
        return;
    }

    for (ll v : child[u]) dfs(v);
    for (ll v : child[u]) dt[v]->merge(dt[u], C[v]);
    median[u] = dt[u]->query();

    /*ll nextc = child[u][0];
    for (ll v : child[u]) if (dt[v]->n > dt[nextc]->n) nextc = v;

    dt[u] = dt[nextc]*/
}

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

    cin >> N >> M;
    for (ll i = 2; i <= N+M; i++) cin >> P[i] >> C[i];

    for (ll i = 2; i <= N+M; i++) child[P[i]].push_back(i);

    C[1] = 0;
    dfs(1);

    ll ans = 0;
    for (ll i = 2; i <= N+M; i++) {
        ll df = median[P[i]] - median[i];
        ans += abs(C[i] - df);
    }

    cout << ans;

    return 0;
}

Compilation message (stderr)

fireworks.cpp: In member function 'void MedianFinder::normalize()':
fireworks.cpp:17:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   17 |         while (low.size() > (n>>1)) {
      |                ~~~~~~~~~~~^~~~~~~~
fireworks.cpp:21:28: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   21 |         while (high.size() > (n>>1)) {
      |                ~~~~~~~~~~~~^~~~~~~~

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