Submission #46956

#	Time	Username	Problem	Language	Result	Execution time	Memory
46956		SpaimaCarpatilor	Wiring (IOI17_wiring)	C++17	100 / 100	186 ms	95692 KiB

wiring

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

using namespace std;

int N, x[200009], col[200009], st[200009], dr[200009], minD[200009];
long long dp[200009], s[200009];
const int INF = 1e9 + 100;

void init (vector < int > &rr, vector < int > &bb)
{
    int pntr1 = 0, pntr2 = 0;
    while (pntr1 < rr.size () || pntr2 < bb.size ())
    {
        if (pntr2 == bb.size () || (pntr1 < rr.size () && rr[pntr1] < bb[pntr2]))
            x[++N] = rr[pntr1], pntr1 ++, col[N] = 0;
        else
            x[++N] = bb[pntr2], pntr2 ++, col[N] = 1;
    }
    int lst[2];
    lst[0] = lst[1] = -1;
    for (int i=1; i<=N; i++)
    {
        if (lst[col[i] ^ 1] == -1) minD[i] = INF;
        else minD[i] = x[i] - lst[col[i] ^ 1];
        lst[col[i]] = x[i];
    }
    lst[0] = lst[1] = -1;
    for (int i=N; i>=1; i--)
    {
        if (lst[col[i] ^ 1] != -1)
            minD[i] = min (minD[i], lst[col[i] ^ 1] - x[i]);
        lst[col[i]] = x[i];
    }
    for (int i=1; i<=N; i++)
        s[i] = s[i - 1] + x[i];
    for (int i=1; i<=N; i++)
        if (col[i] != col[i - 1] || i == 1) st[i] = i;
        else st[i] = st[i - 1];
    for (int i=N; i>=1; i--)
        if (col[i] != col[i + 1] || i == N) dr[i] = i;
        else dr[i] = dr[i + 1];
}
namespace segtree {
    long long arb[2][560009], minQ;

    void Update (int lin, int nod, int st, int dr, int pos, long long val)
    {
        if (st == dr)
        {
            arb[lin][nod] = val;
            return ;
        }
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        if (pos <= mij) Update (lin, f1, st, mij, pos, val);
        else Update (lin, f2, mij + 1, dr, pos, val);
        arb[lin][nod] = min (arb[lin][f1], arb[lin][f2]);
    }

    void Query (int lin, int nod, int st, int dr, int x, int y)
    {
        if (x <= st && dr <= y)
        {
            if (x == st || arb[lin][nod] < minQ)
                minQ = arb[lin][nod];
            return ;
        }
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        if (x <= mij) Query (lin, f1, st, mij, x, y);
        if (mij < y) Query (lin, f2, mij + 1, dr, x, y);
    }

    void performUpdate (int lin, int pos, long long val)
    {
        Update (lin, 1, 1, N, pos, val);
    }

    long long askQuery (int lin, int st, int dr)
    {
        minQ = 1LL << 60;
        st = max (1, st);
        if (st <= dr)
            Query (lin, 1, 1, N, st, dr);
        return minQ;
    }
}
using namespace segtree;

long long min_total_length (vector < int > rr, vector < int > bb)
{
    init (rr, bb);
    dp[0] = 0;
    int lst[2];
    lst[0] = lst[1] = -1;
    for (int i=1; i<=N; i++)
    {
        dp[i] = dp[i - 1] + minD[i];
        if (st[i] > 1)
        {
            int k = st[i] - 1, till = st[k];
            long long mini = 1LL << 60;
            {
                //j >= 2 + 2k - i
                long long curr = askQuery (0, max (st[k], 2 + 2 * k - i), k);
                curr -= 1LL * x[k] * (i - 2 * k - 1);
                if (curr < mini)
                    mini = curr;
            }
            {
                long long curr = askQuery (1, st[k], min (k, 1 + 2 * k - i));
                curr += 1LL * x[k + 1] * (2 * k - i + 1);
                if (curr < mini)
                    mini = curr;
            }
            mini += s[i] - 2LL * s[k];
            if (mini < dp[i])
                dp[i] = mini;
        }
        ///udpates
        performUpdate (0, i, dp[i - 1] + s[i - 1] - 1LL * x[dr[i]] * i);
        performUpdate (1, i, dp[i - 1] + s[i - 1] - 1LL * x[dr[i] + 1] * i);
    }
/*    for (int i=1; i<=N; i++)
        printf ("%lld ", dp[i]);
    printf ("\n");*/
	return dp[N];
}

Compilation message (stderr)

wiring.cpp: In function 'void init(std::vector<int>&, std::vector<int>&)':
wiring.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (pntr1 < rr.size () || pntr2 < bb.size ())
            ~~~~~~^~~~~~~~~~~~
wiring.cpp:13:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (pntr1 < rr.size () || pntr2 < bb.size ())
                                  ~~~~~~^~~~~~~~~~~~
wiring.cpp:15:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pntr2 == bb.size () || (pntr1 < rr.size () && rr[pntr1] < bb[pntr2]))
             ~~~~~~^~~~~~~~~~~~~
wiring.cpp:15:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pntr2 == bb.size () || (pntr1 < rr.size () && rr[pntr1] < bb[pntr2]))
                                     ~~~~~~^~~~~~~~~~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:100:32: warning: unused variable 'till' [-Wunused-variable]
             int k = st[i] - 1, till = st[k];
                                ^~~~

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