Submission #1011134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011134		Roman70	Wiring (IOI17_wiring)	C++17	100 / 100	320 ms	16568 KiB

wiring

// wiring.cpp

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

using namespace std;

#define red 1
#define blue 0
const int N = 200010;

long long seg[4 * N], lazy[4 * N], dp[N];
vector<pair<int,bool>> v;
int n, nxt[N];

long long getmin(int s, int e, int idx, int l, int r) {
    if (s > r || e < l) return 1e18;
    if (s >= l && e <= r) return seg[idx] + lazy[idx];

    lazy[idx * 2] += lazy[idx];
    lazy[idx * 2 + 1] += lazy[idx];
    seg[idx] += lazy[idx];
    lazy[idx] = 0;

    return min(getmin(s, (s + e) / 2, idx * 2, l, r), getmin((s + e) / 2 + 1, e, idx * 2 + 1, l, r));
}

long long update(int s, int e, int idx, int l, int r, long long val) {
    if (s > r || e < l) return seg[idx] + lazy[idx];
    if (s >= l && e <= r) {
        lazy[idx] += val;
        return seg[idx] + lazy[idx];
    }

    lazy[idx * 2] += lazy[idx];
    lazy[idx * 2 + 1] += lazy[idx];
    lazy[idx] = 0;

    return seg[idx] = min(update(s, (s + e) / 2, idx * 2, l, r, val),
                          update((s + e) / 2 + 1, e, idx * 2 + 1, l, r, val));
}

long long min_total_length(vector<int> r, vector<int> b) {
    int j = 0;
    for (int i = 0; i < r.size(); i++) {
        while (j < b.size() && b[j] < r[i]) v.push_back(make_pair(b[j++], blue));
        v.push_back(make_pair(r[i], red));
    }
    while (j < b.size()) v.push_back(make_pair(b[j++], blue));

    n = v.size();
    nxt[n] = n;
    for (int i = n - 1; i >= 0; i--) {
        if (v[i].second != v[i + 1].second) nxt[i] = i + 1;
        else nxt[i] = nxt[i + 1];
    }

    for (int i = n - 1; i >= 0; i--) {
        if (nxt[i] == n) {
            dp[i] = 1e18;
            update(0, n, 1, i, i, dp[i]);
            continue;
        }

        dp[i] = 1e18;

        if (nxt[i] == i + 1) {
            long long sum = 0;
            for (int j = i + 1; j < nxt[i + 1]; j++) {
                update(0, n, 1, j, j, -getmin(0, n, 1, j, j));
                update(0, n, 1, j, j, sum + dp[j]);
                sum += v[j].first - v[i].first;
            }
            for (int j = nxt[i + 1]; j <= nxt[nxt[i + 1]]; j++) {
                update(0, n, 1, j, j, -getmin(0, n, 1, j, j));
                update(0, n, 1, j, j, dp[j] + sum);
                if (j < nxt[nxt[i + 1]]) sum += v[j].first - v[i + 1].first;
            }
            dp[i] = min(dp[i], getmin(0, n, 1, i + 2, nxt[nxt[i + 1]]));
            update(0, n - 1, 1, i, i, dp[i]);
        } else {
            int cur = nxt[i];
            int cur2 = nxt[cur] - 1;
            int num = cur - i;
            long long s = 0;

            if (cur2 - cur < num) {
                if (cur + 1 <= cur2) update(0, n, 1, cur + 1, cur2, v[cur].first - v[i].first);
            } else {
                update(0, n, 1, cur + 1, cur + num - 1, v[cur].first - v[i].first);
                if (cur + num <= cur2) {
                    update(0, n, 1, cur + num, cur2, v[cur - 1].first - v[i].first);
                }
            }
            cur2++;
            if (cur2 - cur < num) s = v[cur].first - v[i].first;
            else s = v[cur - 1].first - v[i].first;
            update(0, n, 1, cur2, nxt[cur2], s);
            dp[i] = getmin(0, n, 1, cur + 1, nxt[cur2]);
            update(0, n, 1, i, i, dp[i]);
        }
    }

    return dp[0];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < r.size(); i++) {
      |                     ~~^~~~~~~~~~
wiring.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         while (j < b.size() && b[j] < r[i]) v.push_back(make_pair(b[j++], blue));
      |                ~~^~~~~~~~~~
wiring.cpp:49:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while (j < b.size()) v.push_back(make_pair(b[j++], blue));
      |            ~~^~~~~~~~~~

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