Submission #1227235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227235		awu	Candies (JOI18_candies)	C++20	0 / 100	2 ms	576 KiB

candies

#include <bits/extc++.h>
#include <immintrin.h>
using namespace std;
using namespace __gnu_pbds;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

#define int long long
#define ll long long
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(x) [](decltype(x) _x) {cerr << #x << " = " << _x << endl; return _x;}(x)
using pii = pair<int, int>;

// const int inf = 1 << 30;
const ll inf = 1ll << 60;
const int MOD = 1e9 + 7;

#if __cplusplus >= 201703L
template <class T, class _ = decltype(begin(declval<T>()))>
enable_if_t<!is_same_v<T, string>, ostream&> operator<<(ostream& out, T a);
template <class T, class U>
ostream& operator<<(ostream& out, pair<T, U> p) {
  return out << "(" << p.f << ", " << p.s << ")";
}
template <class T, class _>
enable_if_t<!is_same_v<T, string>, ostream&> operator<<(ostream& out, T a) {
  string dlm = "";
  out << "{";
  for(auto i : a) {
    out << dlm << i;
    dlm = ", ";
  }
  return out << "}";
}
#endif

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n; cin >> n;
  vector<int> a(n + 2);
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  struct rinfo {
    int l, r; // inc inc
    int csum, nsum;
  };
  map<int, rinfo> rs; // l -> rinfo
  set<pii> rv; // (v, l)
  set<pii> unused; // (v, i)
  for(int i = 1; i <= n; i++) {
    unused.insert({a[i], i});
  }
  int cur = 0;
  for(int j = 1; j <= (n + 1) / 2; j++) {
    int mu = -inf, mr = -inf;
    if(unused.size()) mu = unused.rbegin()->f;
    if(rv.size()) mr = rv.rbegin()->f;
    assert(max(mu, mr) > -inf);
    int touched;
    if(mu > mr) {
      int i = unused.rbegin()->s;
      rs[i - 1] = {i - 1, i + 1, a[i], a[i - 1] + a[i + 1]};
      rv.insert({a[i - 1] + a[i + 1] - a[i], i - 1});
      unused.erase({a[i - 1], i - 1});
      unused.erase({a[i + 1], i + 1});
      unused.erase(prev(unused.end()));
      touched = i - 1;
      cur += a[i];
    } else {
      int l = rv.rbegin()->s;
      auto info = rs[l];
      rs.erase(l);
      rv.erase({info.nsum - info.csum, l});
      info.l--;
      info.r++;
      cur -= info.csum;
      swap(info.csum, info.nsum);
      info.nsum += a[info.l] + a[info.r];
      unused.erase({a[info.l], info.l});
      unused.erase({a[info.r], info.r});
      cur += info.csum;
      rs[l - 1] = info;
      rv.insert({info.nsum - info.csum, l - 1});
      touched = l - 1;
    }
    auto it = rs.find(touched);
    assert(it != rs.end());
    if(next(it) != rs.end()) {
      auto nxt = next(it);
      if(it->s.r == nxt->s.l) {
        rinfo m;
        m.l = it->s.l;
        m.r = nxt->s.r;
        m.csum = it->s.csum + nxt->s.csum;
        m.nsum = it->s.nsum + nxt->s.nsum - a[it->s.r];
        rv.erase({it->s.nsum - it->s.csum, it->s.l});
        rs.erase(it);
        rv.erase({nxt->s.nsum - nxt->s.csum, nxt->s.l});
        rs.erase(nxt);
        rs[m.l] = m;
        rv.insert({m.nsum - m.csum, m.l});
      }
    }
    it = rs.find(touched);
    if(it != rs.begin()) {
      auto prv = prev(it);
      if(prv->s.r == it->s.l) {
        rinfo m;
        m.l = prv->s.l;
        m.r = it->s.l;
        m.csum = prv->s.csum + it->s.csum;
        m.nsum = prv->s.nsum + it->s.nsum - a[prv->s.r];
        rv.erase({prv->s.nsum - prv->s.csum, prv->s.l});
        rs.erase(prv);
        rv.erase({it->s.nsum - it->s.csum, it->s.l});
        rs.erase(it);
        rs[m.l] = m;
        rv.insert({m.nsum - m.csum, m.l});
      }
    }
    cout << cur << endl;
  }
}

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