Submission #592843

#	Time	Username	Problem	Language	Result	Execution time	Memory
592843		alirezasamimi100	Wiring (IOI17_wiring)	C++17	13 / 100	150 ms	12088 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pii = pair<int, int>;
#define pb push_back
#define F first
#define S second
#define lc v<<1
#define rc v<<1|1
const int N = 2e5 + 10;
ll f[N*4],lz[N*4];
void build(int v, int l, int r){
    f[v]=lz[v]=0;
    if(r-l>1){
        int m=(l+r)>>1;
        build(lc,l,m);
        build(rc,m,r);
    }
}
void shift(int v, int l, int r){
    f[v]+=lz[v];
    if(r-l>1){
        lz[lc]+=lz[v];
        lz[rc]+=lz[v];
    }
    lz[v]=0;
}
void upd(int v, int l, int r, int tl, int tr, ll x){
    shift(v,l,r);
    if(l>=tr || tl>=r || tl>=tr) return;
    if(l>=tl && r<=tr){
        lz[v]+=x;
        return shift(v,l,r);
    }
    int m=(l+r)>>1;
    upd(lc,l,m,tl,tr,x);
    upd(rc,m,r,tl,tr,x);
    f[v]=min(f[lc],f[rc]);
}
long long min_total_length(vector<int> r, vector<int> b) {
    vector<pii> vec={{-1,-1}};
    for(int x : r) vec.pb({x,0});
    for(int x : b) vec.pb({x,1});
    sort(vec.begin(),vec.end());
    int n=vec.size()-1;
    ll dp[n+1];
    memset(dp,63,sizeof dp);
    dp[0]=0;
    vector<vector<int>> vv;
    vector<int> t,lv;
    for(int i=1; i<=n; i++){
        t.pb(vec[i].F);
        if(i<n && vec[i].S!=vec[i+1].S){
            vv.pb(t);
            t.clear();
        }
    }
    vv.pb(t);
    int p=-1;
    for(vector<int> vec : vv){
        if(p==-1){
            p=0;
            lv=vec;
            continue;
        }
        int k=lv.size(),m=vec.size();
        ll mn=1e18,lf=lv.back(),rf=vec[0];
        build(1,0,k);
        for(int i=k; i--; ){
            mn=min(mn,dp[p+i]);
            upd(1,0,k,0,i+1,rf-lv[i]);
            upd(1,0,k,i,i+1,mn);
        }
        p+=k;
        for(int i=0; i<min(m,k); i++){
            upd(1,0,k,0,k-i,vec[i]-rf);
            upd(1,0,k,k-i,k,vec[i]-lf);
            dp[p+i+1]=f[1];
        }
        for(int i=k; i<m; i++) dp[p+i+1]=dp[p+i]+vec[i]-lf;
        lv=vec;
    }
    return dp[n];
}

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