제출 #1224801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224801		cpdreamer	Wiring (IOI17_wiring)	C++20	100 / 100	96 ms	21176 KiB

wiring

#include "wiring.h"
#include <vector>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = 1000002022;
#define S second
#define F first
#define pb push_back
#define V vector
#define all(v) v.begin(), v.end()
#define P pair
struct segtree {
private:
    struct node {
        ll val;
    };
    node single(ll v) {
        return {v};
    }
    node neutral={(ll)1e17};
    node merge(node a,node b) {
        return{min(a.val,b.val)};
    }
public:
    int size;
    V<node>query;
    void init(int n) {
        size=1;
        while (size<n)size*=2;
        query.assign(2*size,neutral);
    }
    void set(ll i,ll v,ll x,ll lx,ll rx) {
        if (rx-lx==1) {
            query [x]=single(v);
            return;
        }
        ll  m=(lx+rx)/2;
        if (i<m)
            set(i,v,2*x+1,lx,m);
        else
            set(i,v,2*x+2,m,rx);
        query[x]=merge(query[2*x+1],query[2*x+2]);
    }
    void set(ll i,ll v) {
        set(i,v,0,0,size);
    }
    node calc(ll l,ll r,ll x,ll lx,ll rx) {
        if (lx>=r || rx<=l) {
            return neutral;
        }
        if (l<=lx && rx<=r) {
            return query[x];
        }
        ll m=(lx+rx)/2;
        node a=calc(l,r,2*x+1,lx,m);
        node b=calc(l,r,2*x+2,m,rx);
        return merge(a,b);
    }
    ll calc(ll l,ll r) {
        return calc(l,r,0,0,size).val;
    }
};
ll x[(int)1e6+1],y[(int)1e6+1],pref[(int)1e6+1];
int p[(int)1e6+1];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
    V<P<int,int>>vp;
    vp.pb({0,0});
    for (auto u:r) {
        vp.pb({u,0});
    }
    for (auto u:b) {
        vp.pb({u,1});
    }
    sort(all(vp));
    int n=(int)r.size()+(int)b.size();
    V<ll>a(n+1);V<int>t(n+1);
    for (int i=1;i<=n;i++) {
        a[i]=vp[i].F;
        t[i]=vp[i].S;
    }
    p[0]=-1;
    pref[0]=0;
    for (int i=1;i<=n;i++) {
        pref[i]=pref[i-1]+a[i];
    }
    int curr=-1,id=-1;
    for (int i=n;i>=1;i--) {
        if (t[i]!=curr) {
            curr=t[i];
            id=i;
        }
        x[i]=a[id];
        if (id+1<=n) {
            y[i]=a[id+1];
        }
    }
    curr=-1,id=-1;
    for (int i=1;i<=n;i++) {
        if (t[i]!=curr) {
            curr=t[i];
            id=i;
        }
        p[i]=id;
    }
    V<ll>dp(n+1,1e17);
    dp[0]=0LL;
    segtree tree1,tree2;
    tree1.init(n+1);
    tree2.init(n+1);
    for (ll i=1;i<=n;i++) {
        if (p[i]>1) {
            ll len=i-p[i]+1;
            ll l=p[p[i]-1]-1;
            ll lb=max(l,p[i]-len-1);
            ll c=1e17,c1=1e17;
            if(lb<p[i]-1) {
                c=pref[i]-2LL*pref[p[i]-1]-(len-p[i]+1)*a[p[i]-1]+tree1.calc(lb,p[i]-1);
            }
            if (l<lb) {
                c1=pref[i]-2LL*pref[p[i]-1]+(p[i]-1-len)*a[p[i]]+tree2.calc(l,lb);
            }
            dp[i]=min(c1,c);
        }
        tree1.set(i-1,min(dp[i],dp[i-1])+pref[i-1]-(i-1)*x[i]);
        tree2.set(i-1,min(dp[i],dp[i-1])+pref[i-1]-(i-1)*y[i]);
    }
    return dp[n];
}

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