Submission #1249841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249841		kookeudas	Fireworks (APIO16_fireworks)	C++20	0 / 100	0 ms	328 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct slope_trick{
  long long mn;
  priority_queue<long long> L;
  priority_queue<long long, vector<long long>, greater<long long>> R;
  ll ofs = 0;
  slope_trick(){
    mn = 0;
  }
  long long get_min(){
    return mn;
  }
  void add_right(long long a){
    if (!L.empty()){
      mn += max(L.top() - a, (long long) 0);
    }
    L.push(a);
    R.push(L.top()-ofs);
    L.pop();
  }
  void add_left(long long a){
    if (!R.empty()){
      mn += max(a - (R.top()+ofs), (long long) 0);
    }
    R.push(a-ofs);
    L.push(R.top()+ofs);
    R.pop();
  }
  void conv(long long a){
    long long x = L.top();
    L.pop();
    L.push(x + a);
    ofs+=a;
  }
  slope_trick& operator +=(slope_trick f){
    mn += f.mn;
    while (!f.R.empty()){
      add_right(f.R.top());
      f.R.pop();
    }
    while (!f.L.empty()){
      add_left(f.L.top());
      f.L.pop();
    }
    return *this;
  }
  int size(){
    return L.size() + R.size();
  }
};
int main(){
  int N, M;
  cin >> N >> M;
  vector<int> P(N + M), C(N + M);
  for (int i = 1; i < N + M; i++){
    cin >> P[i] >> C[i];
    P[i]--;
  }
  vector<vector<int>> c(N + M);
  for (int i = 1; i < N + M; i++){
    c[P[i]].push_back(i);
  }
  vector<slope_trick> dp(N + M);
  for (int i = N; i < N + M; i++){
    dp[i].add_left(0);
    dp[i].add_right(0);
  }
  for (int i = N - 1; i >= 0; i--){
    for (int j : c[i]){
      dp[j].conv(C[j]);
    }
    for (int j : c[i]){
      if (dp[j].size() > dp[i].size()){
        swap(dp[i], dp[j]);
      }
      dp[i] += dp[j];
    }
  }
  cout << dp[0].get_min() << endl;
}

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