제출 #362742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
362742		alextodoran	전선 연결 (IOI17_wiring)	C++17	100 / 100	180 ms	21612 KiB

wiring

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "wiring.h"

using namespace std;

typedef long long ll;

const int N_MAX = 200002;

const ll INF = LLONG_MAX / 2;

struct Node
{
    ll x;
    bool color;
};

bool operator < (const Node &a, const Node &b)
{
    return a.x < b.x;
}

int n;

Node v[N_MAX];

int prevL[N_MAX], prevR[N_MAX];
int L[N_MAX], R[N_MAX];

ll sumPref[N_MAX];

ll dp[N_MAX];

ll SGT1[N_MAX * 4], SGT2[N_MAX * 4];

void build (ll SGT[], int node, int l, int r)
{
    if(l == r)
    {
        SGT[node] = INF;
        return;
    }
    int mid = ((l + r) >> 1), lSon = (node << 1), rSon = (lSon | 1);
    build(SGT, lSon, l, mid);
    build(SGT, rSon, mid + 1, r);
    SGT[node] = min(SGT[lSon], SGT[rSon]);
}

void update (ll SGT[], int node, int l, int r, int upos, ll uval)
{
    if(l == r)
    {
        SGT[node] = uval;
        return;
    }
    int mid = ((l + r) >> 1), lSon = (node << 1), rSon = (lSon | 1);
    if(upos <= mid)
        update(SGT, lSon, l, mid, upos, uval);
    else
        update(SGT, rSon, mid + 1, r, upos, uval);
    SGT[node] = min(SGT[lSon], SGT[rSon]);
}

ll query (ll SGT[], int node, int l, int r, int ql, int qr)
{
    if(ql > qr)
        return INF;
    if(ql <= l && r <= qr)
        return SGT[node];
    int mid = ((l + r) >> 1), lSon = (node << 1), rSon = (lSon | 1);
    if(ql <= mid && mid + 1 <= qr)
        return min(query(SGT, lSon, l, mid, ql, qr), query(SGT, rSon, mid + 1, r, ql, qr));
    else if(ql <= mid)
        return query(SGT, lSon, l, mid, ql, qr);
    else
        return query(SGT, rSon, mid + 1, r, ql, qr);
}

ll min_total_length (vector <int> rv, vector <int> bv)
{
    for(int x : rv)
        v[++n] = Node{x, 0};
    for(int x : bv)
        v[++n] = Node{x, 1};
    sort(v + 1, v + n + 1);
    int currL = 1, currR = 0;
    v[n + 1].color = !v[n].color;
    for(int i = 1; i <= n + 1; i++)
    {
        if(i > 1 && v[i].color != v[i - 1].color)
        {
            for(int j = i - 1; j >= 1 && v[j].color == v[i - 1].color; j--)
            {
                L[j] = currL;
                R[j] = currR;
            }
            prevL[i] = currL;
            prevR[i] = currR;
            currL = i;
        }
        else
        {
            prevL[i] = prevL[i - 1];
            prevR[i] = prevR[i - 1];
        }
        currR = i;
    }
    for(int i = 1; i <= n; i++)
        sumPref[i] = sumPref[i - 1] + v[i].x;
    build(SGT1, 1, 1, n);
    build(SGT2, 1, 1, n);
    update(SGT1, 1, 1, n, 1, - v[R[1] + 1].x);
    update(SGT2, 1, 1, n, 1, - v[R[1]].x);
    for(int i = 1; i <= n; i++)
    {
        if(prevL[i] == 0)
            dp[i] = INF;
        else
        {
            int k = prevR[i];
            int l1 = prevL[i], r1 = min(prevR[i], 2 * k - i);
            int l2 = max(prevL[i], 2 * k - i + 1), r2 = prevR[i];
            dp[i] = min({INF,
                         query(SGT1, 1, 1, n, l1, r1) + sumPref[i] - 2 * sumPref[k] + v[k + 1].x * (2 * k - i + 1),
                         query(SGT2, 1, 1, n, l2, r2) + sumPref[i] - 2 * sumPref[k] - v[k].x * (i - 2 * k - 1)});
            update(SGT1, 1, 1, n, i, min(dp[i], dp[i - 1]) + sumPref[i - 1] - v[R[i] + 1].x * i);
            update(SGT2, 1, 1, n, i, min(dp[i], dp[i - 1]) + sumPref[i - 1] - v[R[i]].x * i);
        }
    }
    return dp[n];
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45