Submission #673670

#	Time	Username	Problem	Language	Result	Execution time	Memory
673670		tbzard	Wiring (IOI17_wiring)	C++14	100 / 100	504 ms	16032 KiB

wiring

#include <bits/stdc++.h>
using namespace std;

long long tree[1000000], add[1000000];
void push(int n, int s, int e, long long val){
    tree[n] += val;
    if(s != e){
        add[n+n] += val;
        add[n+n+1] += val;
    }
    add[n] = 0;
}
void update(int n, int s, int e, int l, int r, long long v){
    push(n, s, e, add[n]);
    if(s > r || l > e) return;
    if(l <= s && e <= r){
        push(n, s, e, v);
        return;
    }
    int mid = (s+e)/2;
    update(n+n, s, mid, l, r, v);
    update(n+n+1, mid+1, e, l, r, v);
    tree[n] = min(tree[n+n], tree[n+n+1]);
}
long long query(int n, int s, int e, int l, int r){
    push(n, s, e, add[n]);
    if(s > r || l > e) return 1e18;
    if(l <= s && e <= r) return tree[n];
    int mid = (s+e)/2;
    return min(query(n+n, s, mid, l, r), query(n+n+1, mid+1, e, l, r));
}
long long min_total_length(vector<int> r, vector<int> b){
    vector<pair<int, int> > a;
    for(int i=0;i<r.size();i++) a.push_back(make_pair(r[i], 0));
    for(int i=0;i<b.size();i++) a.push_back(make_pair(b[i], 1));
    a.push_back(make_pair(-1, -1));
    sort(a.begin(), a.end());
    int n = r.size()+b.size();
    vector<int> sz(n+1);
    vector<long long> dp(n+1);
    for(int i=1;i<=n;i++) dp[i] = 1e18;

    long long sum = 0;
    for(int i=1;i<=n;i++){
        if(i == 1 || a[i].second != a[i-1].second) sz[i] = 1, sum = 0;
        else sz[i] = sz[i-1] + 1;

        sum += a[i].first;

        if(i-sz[i] > 0){
            dp[i] = min(dp[i], dp[i-1] + a[i].first - a[i-sz[i]].first);

            int l = i-sz[i], r = i-sz[i]-sz[i-sz[i]];
            if(sz[i] == 1){
                for(int j=l;j>r;j--){
                    update(1, 0, n, r, j-1, -a[j].first);
                    update(1, 0, n, r, j-1, a[i].first);
                    update(1, 0, n, j-1, j-1, dp[j-1]);
                }
            }
            else{
                update(1, 0, n, r, l-1, a[i].first);
                if(sz[i] <= sz[i-sz[i]]){
                    update(1, 0, n, r, l-sz[i], -a[i-sz[i]+1].first);
                }
                update(1, 0, n, l-sz[i]+1, l-1, -a[i-sz[i]].first);
            }
            dp[i] = min(dp[i], query(1, 0, n, r, l-1));
        }
    }
    return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<r.size();i++) a.push_back(make_pair(r[i], 0));
      |                 ~^~~~~~~~~
wiring.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<b.size();i++) a.push_back(make_pair(b[i], 1));
      |                 ~^~~~~~~~~

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