Submission #1259238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259238		Bahamin	Candies (JOI18_candies)	C++20	100 / 100	187 ms	17544 KiB

candies

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;


void solve() {
    int n;
    cin >> n;
    ll a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    int nxt[n];
    int pre[n];
    for (int i = 0; i < n; i++) nxt[i] = i + 1, pre[i] = i - 1;
    set<pair<ll, int>> pq;
    for (int i = 0; i < n; i++) pq.insert({a[i], i});
    ll ans = 0;
    while (pq.size())
    {
        auto x = *pq.rbegin();
        ans += x.first;
        cout << ans << "\n";
        if (nxt[x.second] == n && pre[x.second] == -1)
        {
            break;
        } else if (nxt[x.second] == n)
        {
            pq.erase(x);
            pq.erase({a[pre[x.second]], pre[x.second]});
            if (pre[pre[x.second]] != -1) nxt[pre[pre[x.second]]] = n; 
        } else if (pre[x.second] == -1)
        {
            pq.erase(x);
            pq.erase({a[nxt[x.second]], nxt[x.second]});
            if (nxt[nxt[x.second]] != n) pre[nxt[nxt[x.second]]] = -1;
        } else 
        {
            a[x.second] = a[pre[x.second]] + a[nxt[x.second]] - x.first;
            pq.erase(x);
            pq.erase({a[pre[x.second]], pre[x.second]});
            pq.erase({a[nxt[x.second]], nxt[x.second]});
            pq.insert({a[x.second], x.second});
            pre[x.second] = pre[pre[x.second]];
            nxt[x.second] = nxt[nxt[x.second]];
            if (pre[x.second] != -1) nxt[pre[x.second]] = x.second; 
            if (nxt[x.second] != n) pre[nxt[x.second]] = x.second;
        }
    }
}

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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