oj.uz

Submission #963894

# Submission time Handle Problem Language Result Execution time Memory
963894 2024-04-16T02:05:05 Z abczz Candies (JOI18_candies) C++14
0 / 100
 2 ms 2392 KB 
#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

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.0

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

Subtask #2
0 / 92.0

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