oj.uz

Submission #1035057

# Submission time Handle Problem Language Result Execution time Memory
1035057 2024-07-26T03:36:46 Z juicy Candies (JOI18_candies) C++17
0 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

int n;
int L[N], R[N];
long long a[N];
bool tog[N];

void app(int u) {
  tog[u] = 1;
  L[R[u]] = L[u];
  R[L[u]] = R[u];
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  priority_queue<pair<long long, int>> pq;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    L[i] = i - 1, R[i] = i + 1;
    pq.push({a[i], i});
  }
  long long res = 0;
  for (int i = 1; i <= (n + 1) / 2; ++i) {
    while (pq.size() && tog[pq.top().second]) {
      pq.pop();
    }
    assert(pq.size());
    cout << (res += pq.top().first) << "\n";
    int u = pq.top().second;
    pq.pop();
    int lt = L[u], rt = R[u];
    if (0 < lt && rt <= n) {
      pq.push({a[u] = a[lt] + a[rt] - a[u], u});
    } else {
      app(u);
    }
    app(lt);
    app(rt);
  }
  return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 92.0

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