제출 #1367906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1367906		alexdd	Constellation 3 (JOI20_constellation3)	C++20	100 / 100	260 ms	88600 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e5 + 5;
const int INF = 1e18;
int n, m;
int building[MAXN];

int where[MAXN];
struct info
{
    int id;
    map<int,int> dp;
    vector<int> comp;
    int lazy_add = 0;
    void compact(int h)
    {
        int mnm = 0, trece = 0;
        auto it = dp.begin();
        while(it != dp.end() && (*it).first <= h)
        {
            trece++;
            mnm = min(mnm, (*it).second);
            it = dp.erase(it);
        }
        dp[h] = mnm;
    }
};

info ds[MAXN];

void afis(info&a)
{
    return;

    cerr<<a.id<<":\n";
    for(int x:a.comp)
    {
        cerr<<x<<" ";
        //assert(where[x] == a.id);
    }
    cerr<<"comp\n";

    for(auto it:a.dp) cerr<<it.first<<" "<<it.second + a.lazy_add + INF<<" dp\n";
    cerr<<"\n\n";
}

int curh;

void afis_curh(info&a)
{
    return;
    cerr<<a.id<<" curh: "<<a.dp[curh] + a.lazy_add + INF<<"\n";
}

int unde_id[MAXN];
void merge(info&a, info&b)//merge these two into a
{
    //cerr<<a.id<<" "<<b.id<<" merge ids\n";

    if(a.comp.size() < b.comp.size())
    {
        swap(a, b);
        swap(unde_id[a.id], unde_id[b.id]);
    }

    /*afis_curh(a);
    afis_curh(b);
    cerr<<"\n";*/

    a.compact(curh);
    b.compact(curh);

    afis(a);
    afis(b);

    /*afis_curh(a);
    afis_curh(b);
    cerr<<"\n";*/

    for(auto&it:b.dp)
        it.second += b.lazy_add + INF;

    int old = a.lazy_add;
    a.lazy_add += b.dp[curh];

    for(auto it:b.dp)
    {
        if(it.first != curh)
            a.dp[it.first] = min(a.dp[it.first], (it.second + (a.dp[curh] + old)) - a.lazy_add);
    }

    for(int x:b.comp)
    {
        a.comp.push_back(x);
        where[x] = a.id;
    }

    //afis_curh(a);cerr<<"\n\n\n";

    afis(a);
}

vector<int> ofh[MAXN];
vector<pair<int,int>> stars[MAXN];
bool done[MAXN];
int solve()
{
    for(int i=1;i<=n;i++)
    {
        ofh[building[i]].push_back(i);
    }

    for(int h=1;h<=n;h++)
    {
        curh = h;
        for(int i:ofh[h])
        {
            done[i] = 1;

            int tot = 0;
            for(auto [y,c]:stars[i])
                tot += c;

            for(auto [y,c]:stars[i])
                ds[i].dp[y] = (tot - c) - INF;
            ds[i].dp[curh] = tot - INF;

            ds[i].id = i;
            ds[i].comp = {i};
            where[i] = i;
            unde_id[i] = i;

            if(done[i-1])
            {
                merge(ds[unde_id[where[i-1]]], ds[unde_id[where[i]]]);
            }
            if(done[i+1])
            {
                merge(ds[unde_id[where[i]]], ds[unde_id[where[i+1]]]);
            }
        }
    }

    int root = unde_id[where[1]];
    ds[root].compact(n);
    afis(ds[root]);
    return ds[root].dp[n] + ds[root].lazy_add + INF;
}

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>building[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int x, y, c;
        cin>>x>>y>>c;
        stars[x].push_back({y, c});
    }
    cout<<solve();
    return 0;
}

• 서브태스크 1: 14 / 14
• 서브태스크 2: 21 / 21
• 서브태스크 3: 65 / 65