Submission #963894

#	Time	Username	Problem	Language	Result	Execution time	Memory
963894		abczz	Candies (JOI18_candies)	C++14	0 / 100	2 ms	2392 KiB

candies

#include <iostream>
#include <queue>
#include <array>
#define ll long long

using namespace std;

priority_queue <array<ll, 2>> pq;
bool B[200000], picked[200000];
ll n, f, A[200000], pre[200000], nx[200000];

void maintain(ll u) {
  A[u] = (pre[u] != -1 ? A[pre[u]] : 0) + (nx[u] != n ? A[nx[u]] : 0) - A[u];
}

void linkerase(ll u) {
  B[u] = 1;
  if (pre[u] != -1) nx[pre[u]] = nx[u];
  if (nx[u] < n) pre[nx[u]] = pre[u];
  if (picked[u]) maintain(u);
}

int main() {
  cin >> n;
  for (int i=0; i<n; ++i) {
    cin >> A[i];
    pre[i] = i-1, nx[i] = i+1;
    pq.push({A[i], i});
  }
  for (int i=0; i<(n+1)/2; ++i) {
    while (true) {
      auto [w, u] = pq.top();
      pq.pop();
      if (B[u] || A[u] != w) continue;
      picked[u] = 1;
      f += w;
      if (pre[u] != -1 && nx[u] < n) {
        pq.push({A[pre[u]]+A[nx[u]]-w, u});
        maintain(u);
      }
      if (pre[u] != -1) linkerase(pre[u]);
      if (nx[u] < n) linkerase(nx[u]);
      cout << f << '\n';
      break;
    }
  }
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:32:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |       auto [w, u] = pq.top();
      |            ^

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