Submission #569923

#	Time	Username	Problem	Language	Result	Execution time	Memory
569923		SSRS	Fireworks (APIO16_fireworks)	C++14	100 / 100	413 ms	65088 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
struct slope_trick{
  long long mn;
  priority_queue<long long> L;
  priority_queue<long long, vector<long long>, greater<long long>> R;
  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());
    L.pop();
  }
  void add_left(long long a){
    if (!R.empty()){
      mn += max(a - R.top(), (long long) 0);
    }
    R.push(a);
    L.push(R.top());
    R.pop();
  }
  void conv(long long a){
    long long x = L.top();
    L.pop();
    L.push(x + a);
    long long y = R.top();
    while (!R.empty()){
      R.pop();
    }
    R.push(y + 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: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45