Submission #299301

#	Time	Username	Problem	Language	Result	Execution time	Memory
299301		AlexPop28	Candies (JOI18_candies)	C++11	0 / 100	2 ms	512 KiB

candies

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

// chiar asa de prost implementez sau e gresit? :(

using namespace std;

const int64_t INF = (int64_t)1e18;

template<class T, class Container = vector<T>, class Compare = less<T>>
struct PriorityQueue {
  int sz = 0;
  priority_queue<T, Container, Compare> pq, del;

  void emplace(const T &val) { pq.emplace(val); ++sz; }
  void erase(const T &val) { del.emplace(val); --sz; }
  void pop() { erase(top()); }
  T top() {
    while (!del.empty() && !pq.empty() && del.top() == pq.top()) del.pop(), pq.pop();
    return pq.top();
  }
  int size() const {return sz;}
};

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

  int n; cin >> n;
  vector<int> v(n);
  for (int i = 0; i < n; ++i) {
    cin >> v[i];
  }
  
  PriorityQueue<tuple<int64_t, int64_t, int64_t>> interv;
  for (int i = 0; i < n; ++i) {
    interv.emplace(make_tuple(v[i], i, i));
  }
  
  vector<int64_t> lft(n), rgt(n), val(n);
  for (int i = 0; i < n; ++i) {
    lft[i] = i;
    rgt[i] = i;
    val[i] = v[i];
  }
  
  int64_t ans = 0;
  for (int k = 1; k <= (n + 1) / 2; ++k) {
    int64_t curr, l, r; tie(curr, l, r) = interv.top(); interv.pop();
    ans += curr;
    
    cout << ans << '\n';
    
    curr = -curr;
    int64_t nl = l, nr = r;
    if (l - 1 >= 0) {
      int64_t x = lft[l - 1], y = l - 1;
      assert(val[x] != -INF);
      interv.erase(make_tuple(val[x], x, y));
      curr += val[x];
      nl = x;
    }
    if (r + 1 < n) {
      int64_t x = r + 1, y = rgt[x];
      assert(val[x] != -INF);
      interv.erase(make_tuple(val[x], x, y));
      curr += val[x];
      nr = y;
    }

    interv.emplace(make_tuple(curr, nl, nr));
    val[nl] = curr;
    lft[nr] = nl;
    rgt[nl] = nr;
    
    for (int i = nl + 1; i <= nr; ++i) {
      if (val[i] == -INF) break;
      val[i] = -INF;
    }
    for (int i = nr; i >= nl + 1; --i) {
      if (val[i] == INF) break;
      val[i] = -INF;
    }
  }
}

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