Submission #118171

#	Time	Username	Problem	Language	Result	Execution time	Memory
118171		sealnot123	Wiring (IOI17_wiring)	C++14	100 / 100	197 ms	23088 KiB

wiring

#include "wiring.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
const int N = 200005;
LL seg[2][4*N], dp[N], FF[N], ff[N], BB[N], bb[N], pos[N];
int col[N], last[N], cnt;
int n;
void add(LL val, int idx, int t, int l = 1, int r = n, int now = 1){
    if(l==r){
        seg[t][now] = val;
        return ;
    }
    int m = (l+r)>>1;
    if(idx <= m) add(val, idx, t, l, m, now<<1);
    else add(val, idx, t, m+1, r, now<<1|1);
    seg[t][now] = min(seg[t][now<<1], seg[t][now<<1|1]);
}
LL get(int ll, int rr, int t, int l = 1, int r = n, int now = 1){
    if(ll > rr || l > rr || r < ll) return 1e18;
    if(l >= ll && r <= rr) return seg[t][now];
    int m = (l+r)>>1;
    return min( get(ll, rr, t, l, m, now<<1), get(ll, rr, t, m+1, r, now<<1|1));
}
long long min_total_length(vector<int> A, vector<int> B) {
    n = SZ(A) + SZ(B);
    int a, c, d, i, j, k, l = 0, r = 0;
    while(l < SZ(A) && r < SZ(B)){
        if(A[l] < B[r]){
            pos[++cnt] = A[l++];
        }else{
            pos[++cnt] = B[r++];
            col[cnt] = 1;
        }
    }
    while(l < SZ(A)) pos[++cnt] = A[l++];
    while(r < SZ(B)) pos[++cnt] = B[r++], col[cnt] = 1;
    last[1] = 1;
    for(i=2; i<=n; i++){
        if(col[i] == col[i-1]) last[i] = last[i-1], FF[i] = FF[i-1], ff[i] = ff[i-1];
        else last[i] = i;
        FF[i] += pos[i] - pos[last[i]-1];
        ff[i] += pos[i] - pos[last[i]];
    }
    l = n;
    for(i = n-1; i>0; i--){
        if(col[i] != col[i+1]) l = i+1;
        else BB[i] = BB[i+1], bb[i] = bb[i+1];
        BB[i] += pos[l] - pos[i];
        bb[i] += pos[l-1] - pos[i];
    }
    for(i = 1; i <= n; i++){
        dp[i] = 1e18;
//        printf("xxxxxx%d %d : %d %lld %lld %lld %lld\n", pos[i], col[i], last[i], FF[i], ff[i], BB[i], bb[i]);
        if(last[i] != 1){
            d = i-last[i]+1;
            l = last[last[i]-1];
//            printf("##%d %d = %lld\n",max(l, last[i]-d), last[i]-1, get(max(l, last[i]-d), last[i]-1, 0));
            dp[i] = min(dp[i], get(max(l, last[i]-d), last[i]-1, 0) + FF[i]);
            dp[i] = min(dp[i], get(l, last[i]-d-1, 1) + ff[i]);
        }
//        printf("=====%lld %lld\n", min(dp[i-1],dp[i]) + bb[i], min(dp[i-1],dp[i]) + BB[i]);
        add(min(dp[i-1],dp[i]) + bb[i], i, 0);
        add(min(dp[i-1],dp[i]) + BB[i], i, 1);
//        printf("i %d : %lld\n", i, dp[i]);
    }
	return dp[n];
}
/*
4 5
1 2 3 7
0 4 5 9 10

3 2
1 3 5
2 4
*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:38:9: warning: unused variable 'a' [-Wunused-variable]
     int a, c, d, i, j, k, l = 0, r = 0;
         ^
wiring.cpp:38:12: warning: unused variable 'c' [-Wunused-variable]
     int a, c, d, i, j, k, l = 0, r = 0;
            ^
wiring.cpp:38:21: warning: unused variable 'j' [-Wunused-variable]
     int a, c, d, i, j, k, l = 0, r = 0;
                     ^
wiring.cpp:38:24: warning: unused variable 'k' [-Wunused-variable]
     int a, c, d, i, j, k, l = 0, r = 0;
                        ^

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