Submission #578041

#	Time	Username	Problem	Language	Result	Execution time	Memory
578041		AugustinasJucas	Wiring (IOI17_wiring)	C++14	100 / 100	198 ms	29708 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
#include "wiring.h"
struct medis {
    const long long inf = 1e18;
    vector<long long> val;
    int n;
    medis (int dd) {
        n = dd;
        val.resize(4*n);
        for(auto &x : val) x = inf;
    }
    void change(int v, int nL, int nR, int L, int R, long long x) {
        int mid = (nL + nR) / 2;
        if(L <= nL && nR <= R) {
            val[v] = x;
        }else if(L > nR || nL > R) {
            return ;
        }else {
            change(v*2, nL, mid, L, R, x);
            change(v*2+1, mid+1, nR, L, R, x);
            val[v] = min(val[v*2], val[v*2+1]);
        }
    }

    long long getMin(int v, int nL, int nR, int L, int R) {
        int mid = (nL + nR) / 2;
        if(L <= nL && nR <= R) {
            return val[v];
        }else if(L > nR || nL > R) {
            return inf;
        }else {
            return min(getMin(v*2, nL, mid, L, R), getMin(v*2+1, mid+1, nR, L, R));
        }
    }
};

int n;
const long long inf = 1e18;
vector<int> groupInd;
vector<pair<int, int> > interv;
vector<pair<int, int> > groups;
vector<long long> toRight, toLeft;
vector<long long> ikiL, ikiR;
vector<long long> kaimL, kaimR;
const int dydis = 2e5 + 10;
medis asMax(dydis), jisMax(dydis);
long long f(int l, int r) {
    long long ret = 0;
    ret += toRight[l];
    ret += toLeft[r];
    ret += kaimR[l] * max(ikiR[l], ikiL[r]);
    return ret;

}
void calcToLeft(int l, int r, int ind) {
    int dst = -1;
    if(ind != 0) dst = abs(groups[interv[ind-1].second].first - groups[l].first);
    for(int i = l; i <= r; i++) {
        toLeft[i] = (i == l ? 0ll : toLeft[i-1]) + groups[i].first - groups[l].first;
        ikiL[i] = i - l + 1;
        kaimL[i] = dst;
    }
}
void calcToRight(int l, int r, int ind) {
    int dst = -1;
    if(ind != (int) interv.size() - 1) dst = abs(groups[interv[ind+1].first].first - groups[r].first);
    //cout << "calcToRight, ind = " << ind << ", dst = " << interv[ind+1].first << " - " << r << endl;
    for(int i = r; i >= l; i--) {
        toRight[i] = (i == r ? 0ll : toRight[i+1]) + groups[r].first - groups[i].first;
        ikiR[i] = r - i + 1;
        kaimR[i] = dst;
    }
}
long long min_total_length(vector<int> r, vector<int> b) {
    n = r.size() + b.size();
    for(auto &x : r) {
        groups.push_back({x, 0});
    }
    for(auto &x : b) {
        groups.push_back({x, 1});
    }
    groupInd.resize(n);
    toLeft.resize(n);
    toRight.resize(n);
    ikiL.resize(n);
    ikiR.resize(n);
    kaimL.resize(n);
    kaimR.resize(n);
    sort(groups.begin(), groups.end());
    for(int i = 0; i < n; i++) {
        for(int j = i; j <= n; j++) {
            if(j == n || groups[j].second != groups[i].second) {
                int l = i;
                int r = j-1;

                interv.push_back({l, r});
                for(int h = l; h <= r; h++) {
                    groupInd[h] = (int) interv.size()-1;
                }
                i = j-1;
                break;
            }
        }
    }
    for(int i = 0; i < interv.size(); i++) {
        int l = interv[i].first;
        int r = interv[i].second;
        calcToLeft(l, r, i);
        calcToRight(l, r, i);
    }
    /*
    cout << "intervalai: ";
    for(auto &x : interv) {
        cout << "(" << x.first << ", " << x.second << "), ";
    }
    cout << endl;*/
    vector<long long> dp(n, inf);
//    vector<long long> asMax(n, inf), jisMax(n, inf);
    // dp[-1] = 0;
    asMax.change(1, 0, dydis-1, 0, 0, toRight[0] + kaimR[0] * ikiR[0]);
    jisMax.change(1, 0, dydis-1, 0, 0, toRight[0]);
    for(int i = interv[1].first; i < n; i++) {
        int myInterv = groupInd[i];

        dp[i] = dp[interv[myInterv-1].second] + f(interv[myInterv-1].second, i);

        int ikiManoL = ikiL[i];
        int marker = max(interv[myInterv-1].second - ikiManoL + 1, interv[myInterv-1].first);

        int L = interv[myInterv-1].first;
        int R = interv[myInterv-1].second;
  //      cout << "skaiciuoju dp[" << i << "]. L = " << L << ", R = " << R << ". marker = " << marker << endl;
        /// as busiu maxas intervale [marker; R];
        /// maxas bus jis intervale [L; marker-1];
        dp[i] = min(dp[i], jisMax.getMin(1, 0, dydis-1, marker, R) + kaimL[i] * ikiL[i] + toLeft[i]);
/*        for(int j = marker; j <= R; j++) {
            dp[i] = min(dp[i], jisMax[j] + kaimL[i] * ikiL[i] + toLeft[i]);
        }*/
/*        for(int j = L; j <= marker-1; j++) {
            dp[i] = min(dp[i], asMax[j] + toLeft[i]);
        }*/
        dp[i] = min(dp[i], asMax.getMin(1, 0, dydis-1, L, marker-1) + toLeft[i]);

//        cout << "dp[" << i << "] = " << dp[i] << endl << endl;
    /*
        ret += toRight[l];
        ret += toLeft[r];
        ret += kaimR[l] * max(ikiR[l], ikiL[r]);
    */
        asMax.change(1, 0, dydis-1, i, i, (i == 0 ? 0ll : dp[i-1]) + toRight[i] + kaimR[i] * ikiR[i]);
        jisMax.change(1, 0, dydis-1, i, i, (i == 0 ? 0ll : dp[i-1]) + toRight[i]);
/*
        for(int j = interv[myInterv-1].first; j <= interv[myInterv-1].second; j++) {

            dp[i] = min(dp[i], (j == 0 ? 0ll : dp[j-1]) + f(j, i));
            cout << "gali buti (nuo " << j << ") " << (j == 0 ? 0ll : dp[j-1]) << " + f(" << j << ", " << i << ") = " << f(j, i) << endl;
        }
        cout << "dp[" << i << "] = " << dp[i] << endl << endl;
*/
    }


    return dp[n-1];
}

Compilation message (stderr)

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

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