Submission #1159594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159594		raphaelp	Constellation 3 (JOI20_constellation3)	C++20	100 / 100	513 ms	100364 KiB

constellation3

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

int main()
{
    long long N, tot = 0;
    cin >> N;
    vector<long long> Tab(N);
    vector<pair<long long, long long>> sorted;
    for (long long i = 0; i < N; i++)
    {
        cin >> Tab[i];
        sorted.push_back({Tab[i], i});
    }
    sort(sorted.begin(), sorted.end());
    long long M;
    cin >> M;
    vector<priority_queue<vector<long long>>> Stars(N), highest(N);
    for (long long i = 0; i < M; i++)
    {
        long long x, y, c;
        cin >> x >> y >> c;
        x--;
        tot += c;
        Stars[x].push({-y, c, i});
        highest[x].push({c, i});
    }
    vector<long long> done(N + 1), rep(N + 1), best(N + 1), score(N + 1), dead(M), offset(N);
    for (long long i = 0; i < N; i++)
        rep[i] = i;
    long long ans = 0;
    for (long long i = 0; i < N; i++)
    {
        long long x = sorted[i].second;
        long long left = N, right = N, leftmost = x - 1, rightmost = x + 1, limit = 1000000000;
        if (x > 0 && done[x - 1])
        {
            left = rep[x - 1];
            leftmost -= done[x - 1];
            if (Stars[left].size() > Stars[x].size())
            {
                swap(Stars[x], Stars[left]);
                swap(offset[x], offset[left]);
                swap(highest[x], highest[left]);
            }
            while (!Stars[left].empty())
            {
                vector<long long> temp = Stars[left].top();
                temp[1] += offset[x] - offset[left];
                Stars[x].push(temp);
                highest[x].push({temp[1], temp[2]});
                Stars[left].pop();
            }
        }
        if (x < N - 1 && done[x + 1])
        {
            right = rep[x + 1];
            rightmost += done[x + 1];
            if (Stars[right].size() > Stars[x].size())
            {
                swap(Stars[x], Stars[right]);
                swap(offset[x], offset[right]);
                swap(highest[x], highest[right]);
            }
            while (!Stars[right].empty())
            {
                vector<long long> temp = Stars[right].top();
                temp[1] += offset[x] - offset[right];
                Stars[x].push(temp);
                highest[x].push({temp[1], temp[2]});
                Stars[right].pop();
            }
        }
        if (leftmost >= 0)
            limit = min(limit, Tab[leftmost]);
        if (rightmost < N)
            limit = min(limit, Tab[rightmost]);
        done[leftmost + 1] = rightmost - leftmost - 1;
        done[rightmost - 1] = rightmost - leftmost - 1;
        rep[leftmost + 1] = rep[rightmost - 1] = x;
        score[x] = score[left] + score[right];
        long long low = 0, high = 0;
        while (!Stars[x].empty() && -Stars[x].top()[0] <= limit)
        {
            low = max(low, Stars[x].top()[1] - offset[x]);
            dead[Stars[x].top()[2]] = 1;
            Stars[x].pop();
        }
        while (!highest[x].empty() && dead[highest[x].top()[1]])
            highest[x].pop();
        if (highest[x].size())
            high = highest[x].top()[0] - offset[x];
        offset[x] += low;
        best[x] = score[x] + max(low, high);
        score[x] += low;
        ans = max(ans, best[x]);
    }
    cout << tot - ans << ' ';
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65