Submission #1572946

---

Source Code Expand

#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstring>

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <stack>
#include <queue>

#include <tuple>

#define getchar getchar_unlocked
#define putchar putchar_unlocked

#define _rep(_1, _2, _3, _4, name, ...) name
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))
#define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)

using namespace std;

using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f80 = long double;

int get_int() {
  int c, n;
  while ((c = getchar()) < '0');
  n = c - '0';
  while ((c = getchar()) >= '0') n = n * 10 + (c - '0');
  return n;
}

template <typename T>
class PHeap {
  /*
  - Running Times: N = 10 ** 7
    - Ascend:  0.709 seconds
    - Descend: 0.249 seconds
    - Random:  15.6 seconds
  */
private:
  static constexpr T Inf = (T(1) << (sizeof(T) * 8 - 2)) - 1;
  struct Node {
    Node() {}
    Node(T v) : elem(v), sibling(nullptr), next(nullptr) {}
    T elem; Node *sibling, *next;
    static Node* merge(Node* l, Node* r) {
      if (!l) return r;
      if (!r) return l;
      if (l->elem > r->elem) swap(l, r);
      r->next = l->sibling;
      l->sibling = r;
      return l;
    };
    static Node* merge_list(Node* root) {
      if (!root->sibling) return nullptr;
      Node *a = root->sibling; root = nullptr;
      while (a) {
        Node *b = a->next, *na = nullptr;
        a->next = nullptr;
        if (b) na = b->next, b->next = nullptr;
        a = merge(a, b);
        a->next = root, root = a, a = na;
      }
      Node* s = root->next; root->next = nullptr;
      while (s) {
        Node* u = s->next; s->next = nullptr;
        root = merge(root, s);
        s = u;
      }
      return root;
    }
  };

public:
  class Allocator { // ...
  public:
    Allocator(int N) : N(N), nodes(N), unused(N) { clear_all(); }
    void clear_all() {
      for (int i = 0; i < N; ++i) unused[i] = i;
      unused_pos = 0;
    }
    Node* new_node(T v) { return &(nodes[ unused[unused_pos++] ] = Node(v)); }
    void pop(Node* p) { unused[--unused_pos] = p - nodes.data(); }
  private:
    int N;
    vector<Node> nodes;
    vector<int> unused; int unused_pos;
  };

public:
  PHeap() : root(nullptr) {}
  const T top() const { return root->elem; }
  const T second() {
    return (root->sibling = Node::merge_list(root)) ? root->sibling->elem : Inf;
  }
  bool empty() const { return !root; }
  void push(T v, Allocator& al) { root = Node::merge(root, al.new_node(v)); }
  void meld(PHeap& rhs) { root = Node::merge(root, rhs.root); }
  void pop(Allocator& al) { al.pop(root); root = Node::merge_list(root); }

private:
  Node* root;
};

template <typename T>
i64 optimal_alphabetic_tree(const vector<T>& vs) {
  /*
  - Random:
    - 10 ** 6: 1.387 seconds
    - 10 ** 7: 21.61 seconds
  */
  static constexpr T Inf = (T(1) << (sizeof(T) * 8 - 2)) - 1;
  const int N = vs.size();
  if (N <= 1) return 0;

  vector<T> A(N + 2);
  A[0] = A[N + 1] = Inf;
  for (int i = 1; i <= N; ++i) A[i] = vs[i - 1];

  using Heap = PHeap<T>;
  vector<Heap> heaps(N + 1);
  auto alloc = typename Heap::Allocator(N - 1);
  auto pop = [&] (int k) { heaps[k].pop(alloc); };
  auto push = [&] (int k, T v) { heaps[k].push(v, alloc); };

  vector<int> L(N + 2), R(N + 1);
  vector<T> best(N + 1);

  using P = pair<i64, int>;
  priority_queue< P, vector<P>, greater<P> > que;

  for (int i = 0; i < N + 1; ++i) {
    L[i] = i - 1, R[i] = i + 1;
    best[i] = A[i] + A[i + 1];
    que.emplace(best[i], i);
  }

  auto merge = [&] (int l, int r) {
    heaps[l].meld(heaps[r]);
    R[l] = R[r], L[R[r]] = l, best[r] = 2 * Inf + 1;
    return l;
  };

  i64 ret = 0;
  for (int remaining = N - 1; remaining; --remaining) {
    T w; int k;
    do { tie(w, k) = que.top(); que.pop(); } while (best[k] != w);
    ret += w; 

    int f = 0;
    if (A[k] + A[R[k]] == w) f |= 3;
    else if (heaps[k].top() + A[R[k]] == w) f |= 2, pop(k);
    else if (A[k] + heaps[k].top() == w) f |= 1, pop(k);
    else pop(k), pop(k);

    push(k, w);
    if (f & 1) k = merge(L[k], k);
    if (f & 2) k = merge(k, R[k]);

    T new_w = A[k] + A[R[k]];
    new_w = min(new_w, min(A[k], A[R[k]]) + heaps[k].top());
    new_w = min(new_w, heaps[k].top() + heaps[k].second());
    que.emplace(best[k] = new_w, k);
  }
  return ret;
}

void solve() {
  int N;
  while (~scanf("%d", &N)) {
    vector<int> A(N); rep(i, N) A[i] = get_int();
    printf("%llu\n", optimal_alphabetic_tree<int>(A));
  }
}

int main() {
  clock_t beg = clock();
  solve();
  clock_t end = clock();
  fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);
  return 0;
}

Submission Info

Judge Result