Submission #813317

#	Time	Username	Problem	Language	Result	Execution time	Memory
813317		HaroldVemeno	Wiring (IOI17_wiring)	C++17	100 / 100	73 ms	11360 KiB

wiring

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

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

ll it[400000];
ll itl[400000];
int s = 1;
int n;
int m;

void radd(int l, int r, ll a, int u = 1, int ul = 0, int ur = s) {
    if(r <= ul || ur <= l) return;
    if(l <= ul && ur <= r) {
        itl[u] += a;
        it[u] += a;
        return;
    }
    if(itl[u]) {
        itl[2*u] += itl[u];
        it[2*u] += itl[u];
        itl[2*u+1] += itl[u];
        it[2*u+1] += itl[u];
        itl[u] = 0;
    }
    int um = (ul + ur)/2;
    radd(l, r, a, 2*u  , ul, um);
    radd(l, r, a, 2*u+1, um, ur);
    it[u] = min(it[2*u], it[2*u+1]);
    return;
}

ll rmin(int l, int r, int u = 1, int ul = 0, int ur = s) {
    if(r <= ul || ur <= l) return 1ll << 60;
    if(l <= ul && ur <= r) {
        return it[u];
    }
    if(itl[u]) {
        itl[2*u] += itl[u];
        it[2*u] += itl[u];
        itl[2*u+1] += itl[u];
        it[2*u+1] += itl[u];
        itl[u] = 0;
    }
    int um = (ul + ur)/2;
    return min(rmin(l, r, 2*u, ul, um), rmin(l, r, 2*u+1, um, ur));

}

ll min_total_length(vector<int> r, vector<int> b) {
    n = r.size();
    m = b.size();
    vector<vector<int>> blocks;
    {
        int i = 0;
        int j = 0;
        while(i < n && j < m) {
            if(r[i] < b[j]) {
                blocks.push_back({});
                while(i < n && r[i] < b[j]) {
                    blocks.back().push_back(r[i]);
                    ++i;
                }
            } else {
                blocks.push_back({});
                while(j < m &&  b[j] < r[i]) {
                    blocks.back().push_back(b[j]);
                    j++;
                }
            }
        }
        if(i < n) {
            blocks.push_back({});
            while(i < n) {
                blocks.back().push_back(r[i]);
                ++i;
            }
        }
        if(j < m) {
            blocks.push_back({});
            while(j < m) {
                blocks.back().push_back(b[j]);
                ++j;
            }
        }
    }

    int bc = blocks.size();
    vector<vector<ll>> dp(bc);
    for(int i = 0; i < bc; ++i) {
        int bs = blocks[i].size();
        assert(bs != 0);
        dp[i].resize(bs+1);
        vector<ll> ld(bs+1);
        vector<ll> rd(bs+1);
        for(int j = 1; j < bs; ++j) {
            ld[j] = ld[j-1] + blocks[i][j] - blocks[i][0];
        }
        for(int j = bs-2; j >= 0; --j) {
            rd[j] = rd[j+1] + blocks[i][bs-1] - blocks[i][j];
        }
        dp[i][0] = rd[0];
        dp[i][bs] = ld[bs-1];
        for(int j = 1; j < bs; ++j) {
            dp[i][j] = rd[j] + ld[j-1];
        }
    }

    for(int i = 1; i < dp[0].size(); ++i) {
        dp[0][i] = 1ll << 60;
    }
    ifdeb {
        cout << "\n\n";
        for(auto b : dp) {
            for(auto a : b) {
                cout << a << ' ';
            }
            cout << '\n';
        }
        cout << "\n";
    }
    for(int i = 1; i < bc; ++i) {
        D(i)
        ll lds = dp[i-1].size();
        ll ds = dp[i].size();
        s = 1;
        ll dist = blocks[i].front() - blocks[i-1].back();
        D(dist)
        while(s < lds) s *= 2;
        for(int j = 0; j < lds; ++j) {
            it[s+j] = dp[i-1][j] + (lds-j-1)*dist;
            D(it[s+j]);
            itl[s+j] = 0;
        }
        for(int j = lds; j < s; ++j) {
            it[s+j] = 1ll << 60;
            itl[s+j] = 0;
        }
        for(int j = s-1; j > 0; --j) {
            it[j] = min(it[2*j], it[2*j+1]);
            itl[j] = 0;
        }
        for(int j = 0; j < ds; ++j) {
            radd(max(lds-j, 0ll), lds, dist);
            dp[i][j] += rmin(0, lds);
            D(dp[i][j]);
        }
    }

    ifdeb {
        cout << "\n\n";
        for(auto b : blocks) {
            for(auto a : b) {
                cout << a << ' ';
            }
            cout << '\n';
        }
        cout << "\n";
        for(auto b : dp) {
            for(auto a : b) {
                cout << a << ' ';
            }
            cout << '\n';
        }
        cout << "\n";
    }

	return dp.back().back();
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:122:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for(int i = 1; i < dp[0].size(); ++i) {
      |                    ~~^~~~~~~~~~~~~~

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