Submission #68581

#	Time	Username	Problem	Language	Result	Execution time	Memory
68581		funcsr	Fireworks (APIO16_fireworks)	C++17	100 / 100	1372 ms	169100 KiB

fireworks

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <random>
#include <ctime>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF (1LL<<50)
#define MOD 1000000007
long long diff = 0;
struct DS {
  multiset<long long> left, right;

  void balance() {
    if ((left.size()+right.size())%2 == 0) {
      while (left.size() > right.size()) {
        auto it = --left.end();
        right.insert(*it);
        left.erase(it);
      }
      while (left.size() < right.size()) {
        auto it = right.begin();
        left.insert(*it);
        right.erase(it);
      }
    }
  }
  void add(long long x) {
    if (!right.empty() && x <= *right.begin()) left.insert(x);
    else right.insert(x);
    balance();
  }

  void extend(long long p) {
    if (left.empty()) return;
    auto it = --left.end();
    long long last = *it;
    left.erase(it);
    //cout<<"diff-="<<p<<"\n";
    //diff -= p;
    left.insert(last+p);
    long long lp = *right.begin();
    right.erase(right.begin());

    while (!right.empty() && *right.begin() < INF) {
      auto it = right.begin();
      long long cur = *it;
      //cout<<"diff-=INF\n";
      diff -= INF;
      right.erase(it);
      right.insert(cur+INF);
    }
    right.insert(lp+p);
    assert(left.size() == right.size());
    //balance();
  }
  int size() {
    assert(left.size() == right.size());
    return left.size();
  }
  vector<long long> enumerate() {
    vector<long long> ret;
    for (long long x : left) ret.pb(x);
    for (long long x : right) ret.pb(x);
    return ret;
  }
};

int N, M;
int U[300000], C[300000];
DS dp[300000];

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> M;
  for (int i=1; i<N+M; i++) {
    cin >> U[i] >> C[i];
    U[i]--;
  }
  for (int i=N+M-1; i>0; i--) {
    if (i >= N) dp[i].add(0), dp[i].add(0);
    dp[i].extend(C[i]);
    //cout<<"dp["<<i<<"] = {"; for (long long x : dp[i].enumerate()) cout<<x<<",";cout<<"}\n";

    if (dp[U[i]].size() < dp[i].size()) swap(dp[U[i]], dp[i]);
    vector<long long> vs = dp[i].enumerate();
    for (long long x : vs) dp[U[i]].add(x);
  }
  long long sum = 0;
  //cout<<"dp["<<0<<"] = {"; for (long long x : dp[0].enumerate()) cout<<x<<",";cout<<"}\n";
  long long X = *dp[0].left.rbegin();
  //cout<<"X="<<X<<"\n";
  vector<long long> vs = dp[0].enumerate();
  for (long long x : vs) sum += abs(X-x);
  //cout<<"sum="<<sum<<", diff="<<diff<<"\n";
  sum += diff;
  sum /= 2;
  cout << sum << "\n";
  return 0;
}

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