Submission #1037084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037084		LucaDantas	Candies (JOI18_candies)	C++17	100 / 100	80 ms	18868 KiB

candies

#include <bits/stdc++.h>
using namespace std;

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '['; string sep = ""; for (const auto &x : v) os << sep << x, sep = ", "; return os << ']'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream &os, const set<A> &s) { os << '{'; string sep = ""; for (const auto &x : s) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const map<A, B> &m) { os << '{'; string sep = ""; for (const auto &x : m) os << sep << x.first << " -> " << x.second, sep = ", "; return os << '}'; }

void debug() { cerr << endl; }
template<typename Ini, typename... Fim> void debug(Ini I, Fim... F) { cerr << I; if(sizeof...(F)) cerr << ", "; debug(F...);}
#define db(...) cerr << "DEBUG (" << #__VA_ARGS__ << ") == ", debug(__VA_ARGS__)

constexpr int maxn = 2e5+10;

#define int long long

struct DSU {
    int pai[maxn], peso[maxn], l[maxn], r[maxn], val[maxn], filho[maxn]; // filho eh se tem algum do meu lado ativado
    void init(int a[]) { for(int i = 0; i < maxn; i++) pai[i] = l[i] = r[i] = i, peso[i] = 1, val[i] = a[i]; }
    int find(int x) { return pai[x] == x ? x : pai[x] = find(pai[x]); }
    void merge_dsu(int a, int b) {
        a = find(a), b = find(b);
        if(peso[a] < peso[b])
            swap(a, b);
        pai[b] = a;
        peso[a] += peso[b];
        l[a] = min(l[a], l[b]);
        r[a] = max(r[a], r[b]);
    }
    void merge(int p, int f1, int f2) {
        // nao eh pra precisar dar find nessa funcao, isso eu farei antes de chamar pros caras necessarios
        int new_val = val[f1] + val[f2] - val[p];
        // filho nao sobe, sempre ta salvo no do pai e eh usado quando vai dar merge, entao n faz nada com ele
        merge_dsu(p, f1);
        merge_dsu(p, f2);
        int raiz = find(p);
        val[raiz] = new_val;
        filho[raiz] = 0; // nao tem mais nenhum filho, deu merge
    }
    bool set_filho(int colocar, int p) { // retorna true se deu merge
        colocar = find(colocar), p = find(p);
        if(!filho[p])
            return (filho[p] = colocar, false);

        int f2 = find(filho[p]);
        merge(p, colocar, f2);

        return true;
    }
} dsu;

int a[maxn];

bool disponiveis[maxn];

priority_queue<pair<int,int>> q;

int32_t main() {
    int n; scanf("%lld", &n);
    for(int i = 1; i <= n; i++)
        scanf("%lld", a+i), q.push({a[i], i});

    memset(disponiveis, 1, sizeof disponiveis);

    dsu.init(a);

    long long ans = 0;
    while(q.size()) {
        auto [val, colocar] = q.top();
        q.pop();
        colocar = dsu.find(colocar);
        int l = dsu.l[colocar], r = dsu.r[colocar];
        // db("TOME PORRA", val, colocar, l, r);
        if(disponiveis[l-1] && disponiveis[r+1]) {
            ans += dsu.val[colocar];
            disponiveis[l] = disponiveis[r] = 0;
            // db("AGORA", ans);
            printf("%lld\n", ans);
            // k++; // so nesse caso q eu conto mais pra resposta
            continue;
        }
        int k = disponiveis[l-1] ? r+1 : l-1; // sei com certeza que pelo menos um deles ta disponivel
        // db("merge", colocar, k);
        if(dsu.set_filho(colocar, k)) {
            // db("CARALLLHOOOO");
            // ja consegui dar um merge, nem continuo pra colocar filho no outro, so recoloco ele na fila e fds
            colocar = dsu.find(colocar);
            q.push({dsu.val[colocar], colocar});
        }
    }
}

Compilation message (stderr)

candies.cpp: In function 'int32_t main()':
candies.cpp:59:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     int n; scanf("%lld", &n);
      |            ~~~~~^~~~~~~~~~~~
candies.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%lld", a+i), q.push({a[i], i});
      |         ~~~~~^~~~~~~~~~~~~

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