Submission #1309111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309111		dorkikann	Candies (JOI18_candies)	C++20	100 / 100	75 ms	10668 KiB

candies

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

const int N = 2e5 + 5;

ll A[N];

int Point[N];
ll Value[N];
pair<int, int> Segment[N];

int Find(int u) {
    if(u == Point[u])
        return u;
    return Point[u] = Find(Point[u]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a == b)
        return;
    
    Point[a] = b;
    Segment[b].first = min(Segment[b].first, Segment[a].first);
    Segment[b].second = max(Segment[b].second, Segment[a].second);
    Value[b] += Value[a];
}

bool Correct(pair<ll, int> x)
{
    int u = Find(x.second);

    if((Segment[u].second - Segment[u].first) % 2 == 1)
        return false;

    return (Value[u] == x.first);
}

void Fix(int u, int n)
{  
    u = Find(u);
    
    int a = max(1, Segment[u].first - 1);
    int b = min(n, Segment[u].second + 1);

    Value[u] *= -1;
    Union(a, u);
    Union(u, b);
}

void Solve(int n)
{
    priority_queue<pair<ll, int>> PQ;
    
    for(int i = 1; i <= n; i++) {
        Point[i] = i;
        Segment[i] = {i, i};

        Value[i] = A[i];
        PQ.push({A[i], i});
    }

    ll sol = 0;
    for(int i = 0; i < (n+1)/2; i++) {
        pair<ll, int> add;
        do {
            add = PQ.top();
            PQ.pop();
        } while(!Correct(add));

        sol += add.first;
        Fix(add.second, n);
        PQ.push({Value[Find(add.second)], Find(add.second)});

        cout << sol << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

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

    Solve(n);
    return 0;
}

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