Submission #763586

#	Time	Username	Problem	Language	Result	Execution time	Memory
763586		boris_mihov	Wiring (IOI17_wiring)	C++17	100 / 100	135 ms	17944 KiB

wiring

#include "wiring.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>
 
typedef long long llong;
const int MAXN = 200000 + 10;
const llong LLINF = 1e18;
const int INF = 1e9;

int n, m;
struct SegmentTree
{
    llong tree[4*MAXN];
    void update(int l, int r, int node, int queryPos, llong queryValue)
    {
        if (l == r)
        {
            tree[node] = queryValue;
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryValue);
        else update(mid + 1, r, 2*node + 1, queryPos, queryValue);
        tree[node] = std::min(tree[2*node], tree[2*node + 1]);
    }

    llong query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        llong res = LLINF;
        int mid = (l + r) / 2;
        if (queryL <= mid) res = std::min(res, query(l, mid, 2*node, queryL, queryR));
        if (mid + 1 <= queryR) res = std::min(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
        return res;
    }

    void update(int pos, llong val)
    {
        update(1, n + m + 1, 1, pos, val);
    }

    llong query(int l, int r)
    {
        return query(1, n + m + 1, 1, l, r);
    }
};

llong dp[MAXN];
llong suff[MAXN];
llong prefix[MAXN];
SegmentTree leftTree; // left is longer
SegmentTree rightTree; // right is longer
std::pair <int,bool> a[MAXN];
int inBucket[MAXN];
int right[MAXN];
int left[MAXN];

llong min_total_length(std::vector <int> R, std::vector <int> B) 
{
    n = R.size();
    m = B.size();

    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = {R[i - 1], false};
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        a[n + i] = {B[i - 1], true};
    }

    std::sort(a + 1, a + 1 + n + m);
    a[0].second = a[1].second ^ 1;
    int cnt = 0;

    for (int i = 1 ; i <= n + m ; ++i)
    {
        if (a[i].second == a[i - 1].second)
        {
            right[cnt] = i;
        } else
        {
            cnt++;
            left[cnt] = right[cnt] = i;
        }

        inBucket[i] = cnt;
    }

    for (int i = 1 ; i <= n + m ; ++i)
    {
        prefix[i] = prefix[i - 1] + a[i].first;
    } 

    leftTree.update(1, -a[left[2]].first);
    rightTree.update(1, -a[right[1]].first);
    for (int i = 1 ; i <= n + m ; ++i)
    {
        if ((i > 1 && inBucket[i] != inBucket[i - 1]) || (i > 2 && inBucket[i - 2] != inBucket[i - 1]))
        {
            for (int j = i - 2 ; j >= left[inBucket[i - 2]] ; --j)
            {
                dp[j] = std::min(dp[j], dp[j + 1]);
            }

            for (int j = left[inBucket[i - 2]] ; j < i ; ++j)
            {
                leftTree.update(j + 1, prefix[j] + dp[j] - 1LL * (j + 1) * a[left[inBucket[j + 1] + 1]].first);
                rightTree.update(j + 1, prefix[j] + dp[j] - 1LL * (j + 1) * a[right[inBucket[j + 1]]].first);
            }

            dp[i] = 0;
        }

        if (inBucket[i] == 1)
        {
            dp[i] = LLINF;
        } else
        {
            int prevL = left[inBucket[i] - 1];
            int prevR = right[inBucket[i] - 1];

            if (i - prevR >= prevR - prevL + 1)
            {
                dp[i] = rightTree.query(prevL, prevR) + 1LL * (2 * prevR + 1 - i) * a[prevR].first;
            } else
            {
                int equalPos = prevR - (i - prevR - 1);
                dp[i] = rightTree.query(equalPos, prevR) + 1LL * (2 * prevR + 1 - i) * a[prevR].first;
                dp[i] = std::min(dp[i], leftTree.query(prevL, equalPos - 1) + 1LL * (2 * prevR + 1 - i) * a[prevR + 1].first);
            }
            
            dp[i] += prefix[i] - 2 * prefix[prevR]; 
        }
    }

    return dp[n + m];
}

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