oj.uz

답안 #299291

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
299291 2020-09-14T16:24:38 Z AlexPop28 Candies (JOI18_candies) C++11
0 / 100
 2 ms 512 KB 
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

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;
      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];
      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;
  }
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -