Submission #879278

#	Time	Username	Problem	Language	Result	Execution time	Memory
879278		NeroZein	Candies (JOI18_candies)	C++17	100 / 100	293 ms	20308 KiB

candies

#include "bits/stdc++.h"
using namespace std;
 
#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif
 
const int MAX_N = 2e5 + 5; 
 
int A[MAX_N]; 
int L[MAX_N], R[MAX_N]; 
long long Val[MAX_N];
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  for (int i = 1; i <= N; ++i) {
    cin >> A[i]; 
  }
  set<array<long long, 3>> Set; 
  for (int i = 1; i <= N; ++i) {
    L[i] = R[i] = i;
    Val[i] = A[i]; 
    Set.insert({-A[i], i, i}); 
  }
  
  long long ans = 0; 
  for (int i = 1; i <= (N + 1) / 2; ++i) {
    auto [val, l, r] = *Set.begin(); 
    Set.erase({val, l, r}); 
    ans += -val; 
    int newL = L[l - 1];
    int newR = R[r + 1]; 
    //deb(L[0]) cout << '\n';
    //deb(l) deb(r) deb(newL) deb(newR) cout << '\n';
    long long newVal = Val[L[l - 1]] + Val[r + 1] + val; 
    if (L[l - 1]) {
      int tl = L[l - 1]; 
      Set.erase({-Val[tl], tl, l - 1});      
    }
    if (R[r + 1]) {
      int tr = R[r + 1]; 
      Set.erase({-Val[r + 1], r + 1, tr});      
    }
    if (newL && newR) {
      Set.insert({-newVal, newL, newR});       
    }
    if (newR) {
      L[newR] = newL;      
    }
    R[newL] = newR;
    Val[newL] = newVal; 
    //deb(Set) cout << '\n';
    cout << ans << '\n'; 
  }
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92