oj.uz

Submission #946398

# Submission time Handle Problem Language Result Execution time Memory
946398 2024-03-14T15:55:15 Z Sokol080808 Candies (JOI18_candies) C++17
100 / 100
 651 ms 29720 KB 
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using ll = long long;
using ull = unsigned long long;
using ld = long double;

const ll INF = 1e18;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    int mxc = (n + 1) / 2;
    
    set<array<ll, 3>> segs;
    set<array<ll, 3>> best;
    for (int i = 1; i <= n; i++) {
        segs.insert({i, i, a[i]});
        best.insert({a[i], i, i});
    }

    ll ans = 0;
    for (int iteration = 0; iteration < mxc; iteration++) {
        auto it = prev(best.end());
        auto [add, l, r] = *it;
        segs.erase({l, r, add});
        best.erase({add, l, r});
        ans += add;
        cout << ans << '\n';

        if (best.empty()) break;

        auto it2 = segs.lower_bound({l, INF, INF});
        if (it2 == segs.end()) {
            it2 = prev(it2);
            best.erase({(*it2)[2], (*it2)[0], (*it2)[1]});
            segs.erase(it2);
            continue;
        }
        if (it2 == segs.begin()) {
            best.erase({(*it2)[2], (*it2)[0], (*it2)[1]});
            segs.erase(it2);
            continue;
        }
        
        add = -add;
        auto nxt = segs.lower_bound({l, INF, INF});
        if (nxt != segs.end()) {
            add += (*nxt)[2];
            r = (*nxt)[1];
            best.erase({(*nxt)[2], (*nxt)[0], (*nxt)[1]});
            segs.erase(nxt);
        }
        auto prv = segs.lower_bound({l, INF, INF});
        if (prv != segs.begin()) {
            prv = prev(prv);
            add += (*prv)[2];
            l = (*prv)[0];
            best.erase({(*prv)[2], (*prv)[0], (*prv)[1]});
            segs.erase(prv);
        }

        segs.insert({l, r, add});
        best.insert({add, l, r});
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 3 ms 744 KB Output is correct
5 Correct 3 ms 740 KB Output is correct
6 Correct 3 ms 744 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 3 ms 600 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 3 ms 740 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 3 ms 604 KB Output is correct
17 Correct 4 ms 600 KB Output is correct
18 Correct 4 ms 604 KB Output is correct
19 Correct 3 ms 604 KB Output is correct
20 Correct 3 ms 740 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 3 ms 744 KB Output is correct
5 Correct 3 ms 740 KB Output is correct
6 Correct 3 ms 744 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 3 ms 600 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 3 ms 740 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 3 ms 604 KB Output is correct
17 Correct 4 ms 600 KB Output is correct
18 Correct 4 ms 604 KB Output is correct
19 Correct 3 ms 604 KB Output is correct
20 Correct 3 ms 740 KB Output is correct
21 Correct 586 ms 29524 KB Output is correct
22 Correct 563 ms 29520 KB Output is correct
23 Correct 603 ms 29340 KB Output is correct
24 Correct 399 ms 29648 KB Output is correct
25 Correct 371 ms 29128 KB Output is correct
26 Correct 364 ms 29264 KB Output is correct
27 Correct 377 ms 29520 KB Output is correct
28 Correct 373 ms 29524 KB Output is correct
29 Correct 378 ms 29364 KB Output is correct
30 Correct 388 ms 29412 KB Output is correct
31 Correct 397 ms 29720 KB Output is correct
32 Correct 416 ms 29424 KB Output is correct
33 Correct 483 ms 29268 KB Output is correct
34 Correct 459 ms 29200 KB Output is correct
35 Correct 485 ms 29268 KB Output is correct
36 Correct 651 ms 29448 KB Output is correct
37 Correct 613 ms 29616 KB Output is correct
38 Correct 585 ms 29548 KB Output is correct
39 Correct 381 ms 29292 KB Output is correct
40 Correct 381 ms 29108 KB Output is correct
41 Correct 396 ms 29168 KB Output is correct
42 Correct 386 ms 29540 KB Output is correct
43 Correct 407 ms 29396 KB Output is correct
44 Correct 369 ms 29444 KB Output is correct
45 Correct 424 ms 29564 KB Output is correct
46 Correct 453 ms 29520 KB Output is correct
47 Correct 388 ms 29488 KB Output is correct
48 Correct 474 ms 29264 KB Output is correct
49 Correct 487 ms 29284 KB Output is correct
50 Correct 466 ms 29104 KB Output is correct