Submission #991839

#	Time	Username	Problem	Language	Result	Execution time	Memory
991839		caterpillow	Candies (JOI18_candies)	C++17	100 / 100	91 ms	15816 KiB

candies

#include <bits/stdc++.h>
#include <queue>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
#define vt vector
#define f first
#define s second
#define all(x) x.begin(), x.end() 
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = o.size(); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

void _print() {
    cerr << "\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
    cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef LOCAL
#define dbg(x...) cerr <<__func__ << ":" <<__LINE__ << " " << #x << " = "; _print(x);
#else
#define dbg(x...)
#endif

/*

consider how the solution changes when you add a new candy

case 1: a new candy is taken and the previous candy dont move
case 2: a new candy is taken and previous candy need to be shifted

    consider the current taken candy
    ...X...
    say we try to take an adjacent candy
    ...XO..
    this means that the X needs to move somewhere
    say the X moves here
    .X..O..
    this is bad, however, since 
    .O.X... 
    would be strictly better
    hence, whenver you move a piece of candy, a consecutive "sequence" of candy get shuffled 

make a pq of ranges
a valid range is an odd length range of alternating 0's and 1's, with two 0's on either side

*/

struct DSU {
    vt<int> e, l, r;
    void init(int n) {
        e = l = vt<int>(n, -1);
        iota(all(l), 0);
        r = l;
    }
    int find(int x) {
        return e[x] < 0 ? x : e[x] = find(e[x]);
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        int nl = min(l[x], l[y]);
        int nr = max(r[x], r[y]);
        if (e[x] < e[y]) swap(x, y);
        e[y] += e[x];
        e[x] = y;
        l[y] = nl;
        r[y] = nr;
    }
};

int n;
ll arr[200005], sfx[200005];

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n;
    F0R (i, n) cin >> arr[i];
    F0R (i, n) sfx[i] = arr[i] * (i % 2 == 0 ? 1 : -1);
    ROF (i, 0, n) sfx[i] += sfx[i + 1];

    DSU dsu;
    dsu.init(n);

    using t3 = tuple<ll, ll, ll>;
    priority_queue<t3> pq;
    F0R (i, n) {
        pq.push({arr[i], i, i});
    }

    vt<bool> used(n);

    auto good = [&] (t3 x) {
        auto [c, l, r] = x;
        dbg(c, l, r);
        return !used[l] && !used[r] && (l == 0 || !used[l - 1]) && (r == n - 1 || !used[r + 1]);
    };

    ll tot = 0;
    FOR (_, 1, (n + 3) / 2) {
        t3 cur = pq.top();
        while (!good(cur)) pq.pop(), assert(pq.size()), cur = pq.top();
        pq.pop();
        auto [v, l, r] = cur;
        tot += v;
        used[l] = used[r] = 1;
        if (l) dsu.unite(l, l - 1);
        if (r + 1 < n) dsu.unite(r, r + 1);
        int x = dsu.find(l);
        int nl = dsu.l[x];
        int nr = dsu.r[x];
        pq.push({(sfx[nl] - sfx[nr + 1]) * (nl % 2 == 0 ? 1 : -1), nl, nr});
        cout << tot << endl;
        dbg(tot);
        dbg(used);
        dbg(l, r, nl, nr);
    }
}

Compilation message (stderr)

candies.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   93 | main() {
      | ^~~~

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