Submission #745645

#	Time	Username	Problem	Language	Result	Execution time	Memory
745645		MilosMilutinovic	Candies (JOI18_candies)	C++14	100 / 100	535 ms	29644 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, a[N];
set<pair<ll, int>> val;
set<pair<int, ll>> pos;
void add(int i, ll v) {
    val.emplace(v, i);
    pos.emplace(i, v);
}
void rem(int i, ll v) {
    val.erase(val.find({v, i}));
    pos.erase(pos.find({i, v}));
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) add(i, a[i]);
    add(0, -inf); add(n + 1, -inf);
    ll ans = 0;
    for (int i = 0; i < (n + 1) / 2; i++) {
        auto it = prev(val.end());
        pair<ll, int> f = *it;
        ans += f.first;
        auto ti = pos.lower_bound({f.second, -inf});
        printf("%lld\n", ans);
        pair<int, ll> x = *prev(ti);
        pair<int, ll> y = *ti;
        pair<int, ll> z = *next(ti);
        rem(x.first, x.second);
        rem(y.first, y.second);
        rem(z.first, z.second);
        add(y.first, x.second + z.second - y.second);
    }
    return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
candies.cpp:19:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
      |                                  ~~~~~^~~~~~~~~~~~~

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