oj.uz

Submission #569909

# Submission time Handle Problem Language Result Execution time Memory
569909 2022-05-28T07:21:28 Z SSRS Fireworks (APIO16_fireworks) C++14
0 / 100
 1 ms 212 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -