Submission #1307684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307684		ereonzis	Candies (JOI18_candies)	C++20	100 / 100	243 ms	19928 KiB

candies

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
namespace debug {
template <class c> struct rge { c b, e; };
template <class c> rge<c> range(c i, c j) { return rge<c>{i, j}; }
template <class c> char spk(...);
template <class c> auto spk(c *a) -> decltype(cerr << *a, 0);
struct stream {
  ~stream() { cerr << endl; }
  template <class c>
  typename enable_if<sizeof spk<c>(0) != 1, stream &>::type operator<<(c i) {
    cerr << boolalpha << i;
    return *this;
  }
  template <class c>
  typename enable_if<sizeof spk<c>(0) == 1, stream &>::type operator<<(c i) {
    return *this << range(begin(i), end(i));
  }
  template <class a, class b> stream &operator<<(pair<a, b> p) {
    return *this << "(" << p.first << ", " << p.second << ")";
  }
  template <class c> stream &operator<<(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; it++)
      *this << ", " + 2 * (it == d.b) << *it;
    return *this << "]";
  }
  stream &_dbg(const string &s, int i, int b) { return *this; }
  template <class c, class... cs>
  stream &_dbg(const string &s, int i, int b, c arg, cs... args) {
    if (i == (int)(s.size()))
      return (*this << ": " << arg);
    b += (s[i] == '(') + (s[i] == '[') + (s[i] == '{') - (s[i] == ')') -
         (s[i] == ']') - (s[i] == '}');
    return (s[i] == ',' && b == 0)
               ? (*this << ": " << arg << "     ")._dbg(s, i + 1, b, args...)
               : (s[i] == ' ' ? *this : *this << s[i])
                     ._dbg(s, i + 1, b, arg, args...);
  }
};
} // namespace debug
#ifdef DEBUG
#define dout debug::stream()
#define dbg(...) ((dout << "line:" << __LINE__ << " >> ")._dbg(#__VA_ARGS__, 0, 0, __VA_ARGS__))
#else
#define dout
#define dbg(...)
#endif
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (b); i >= (a); i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define SZ(x) (int)(x).size()
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using vi = vector<int>;

const int MAXN = 200'007;
const ll INF = 1e18;
int A[MAXN], L[MAXN], R[MAXN];
ll P[2][MAXN];
set<pair<ll, pii>, greater<pair<ll, pii>>> S;
int n;
ll ans = 0;

ll sum(int l, int r) {
    if (r < l) return 0;
    return P[l%2][r] - P[l%2][l-1];
}

pair<ll, pii> opp(int l, int r) {
    if (l == 1 || r == n) return mp(-INF, mp(0, 0));
    return mp(sum(l-1, r+1) - sum(l, r), mp(l-1, r+1));
}

// [l, s], [s+2, r]
void merge(int l, int s, int r) {
    dbg("merge", l, s, r);
    S.erase(opp(l, s)); S.erase(opp(s+2, r));
    L[s] = R[s] = L[s+2] = R[s+2] = 0;
    L[r] = l; R[l] = r;
    S.insert(opp(l, r));
}


void set_interval(int l, int r) {
    ans += sum(l, r) - sum(l+1, r-1);
    S.insert(opp(l, r));
    S.erase(mp(A[r+1], mp(r+1, r+1)));
    S.erase(mp(A[l-1], mp(l-1, l-1)));
    if (R[l+1]) {
        L[R[l+1]] = 0; R[l+1] = 0;
    }
    if (L[r-1]) {
        R[L[r-1]] = 0; L[r-1] = 0;
    }
    if (l >= 3 && L[l-2]) {
        int lb = L[l-2];
        merge(lb, l-2, r);
        l = lb;
    }
    if (r+2 <= n && R[r+2]) {
        int rb = R[r+2];
        merge(l, r, R[r+2]);
        r = rb;
    }
    L[r] = l; R[l] = r;
}


int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin >> n;
    rep(i, 1, n) cin >> A[i];
    rep(i, 1, n) {
        rep(j, 0, 1) P[j][i] = P[j][i-1];
        P[i%2][i] += A[i];
    }
    rep(i, 1, n) S.insert(mp(A[i], mp(i, i)));
    rep(j, 1, (n+1)/2) {
        dbg(S);
        auto [val, i] = *S.begin();
        S.erase(S.begin());
        dbg(val, i);
        set_interval(i.st, i.nd);
        cout << ans << '\n';
    }

    return 0;
}

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