oj.uz

Submission #991839

# Submission time Handle Problem Language Result Execution time Memory
991839 2024-06-03T08:37:01 Z caterpillow Candies (JOI18_candies) C++17
100 / 100
 91 ms 15816 KB 
#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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2536 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 1 ms 2524 KB Output is correct
11 Correct 2 ms 2540 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2536 KB Output is correct
17 Correct 1 ms 2520 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 3 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2536 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 1 ms 2524 KB Output is correct
11 Correct 2 ms 2540 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2536 KB Output is correct
17 Correct 1 ms 2520 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 3 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 91 ms 15424 KB Output is correct
22 Correct 86 ms 14776 KB Output is correct
23 Correct 86 ms 14776 KB Output is correct
24 Correct 66 ms 15136 KB Output is correct
25 Correct 67 ms 15292 KB Output is correct
26 Correct 64 ms 15440 KB Output is correct
27 Correct 70 ms 15040 KB Output is correct
28 Correct 72 ms 15816 KB Output is correct
29 Correct 72 ms 15548 KB Output is correct
30 Correct 73 ms 14744 KB Output is correct
31 Correct 76 ms 15552 KB Output is correct
32 Correct 77 ms 15288 KB Output is correct
33 Correct 73 ms 15308 KB Output is correct
34 Correct 74 ms 15028 KB Output is correct
35 Correct 78 ms 15552 KB Output is correct
36 Correct 81 ms 15260 KB Output is correct
37 Correct 89 ms 15308 KB Output is correct
38 Correct 86 ms 15284 KB Output is correct
39 Correct 62 ms 15560 KB Output is correct
40 Correct 64 ms 15292 KB Output is correct
41 Correct 71 ms 14600 KB Output is correct
42 Correct 88 ms 15564 KB Output is correct
43 Correct 71 ms 15400 KB Output is correct
44 Correct 88 ms 15552 KB Output is correct
45 Correct 80 ms 15532 KB Output is correct
46 Correct 73 ms 15808 KB Output is correct
47 Correct 69 ms 15300 KB Output is correct
48 Correct 91 ms 14516 KB Output is correct
49 Correct 75 ms 15296 KB Output is correct
50 Correct 75 ms 15560 KB Output is correct