Submission #569909

#	Time	Username	Problem	Language	Result	Execution time	Memory
569909		SSRS	Fireworks (APIO16_fireworks)	C++14	0 / 100	1 ms	212 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
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<long long> mn(N + M, 0);
  vector<priority_queue<long long>> L(N + M);
  vector<priority_queue<long long, vector<long long>, greater<long long>>> R(N + M);
  for (int i = N; i < N + M; i++){
    L[i].push(0);
    R[i].push(0);
  }
  for (int i = N - 1; i >= 0; i--){
    for (int j : c[i]){
      long long x = L[j].top();
      L[j].pop();
      L[j].push(x + C[j]);
      priority_queue<long long, vector<long long>, greater<long long>> R2;
      while (!R[j].empty()){
        R2.push(R[j].top() + C[j]);
        R[j].pop();
      }
      R[j] = R2;
      mn[i] += mn[j];
      while (!R[j].empty()){
        long long a = R[j].top();
        R[j].pop();
        if (!L[i].empty()){
          mn[i] += max(L[i].top() - a, (long long) 0);
        }
        L[i].push(a);
        R[i].push(L[i].top());
        R[i].pop();
      }
      while (!L[j].empty()){
        long long a = L[j].top();
        L[j].pop();
        if (!R[i].empty()){
          mn[i] += max(a - R[i].top(), (long long) 0);
        }
        R[i].push(a);
        L[i].push(R[i].top());
        R[i].pop();
      }
    }
  }
  cout << mn[0] << endl;
}

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