Submission #236224

#	Time	Username	Problem	Language	Result	Execution time	Memory
236224		MarcoMeijer	Wiring (IOI17_wiring)	C++14	100 / 100	715 ms	33928 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
 
//macros
typedef long long ll;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(ll a=ll(b); a<ll(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(ll a=ll(c-1); a>=ll(b); a--)
#define INF 1e18
#define pb push_back
#define fi first
#define se second
#define sz size()
 
 
// min segment tree library

template <class T=int, T MAX=1000000000, T DEF=0>
class MinSegmentTree {
public:
	void resize(int _size) {
		size = _size;
		SEG.assign(size*4, DEF);
		LAZ.assign(size*4, 0);
	}
	void add(int i, int j, T x, T lazy, int p, int l, int r) {
		SEG[p] += lazy;
		LAZ[p] += lazy;
		if(j < l || i > r) return;
		if(i <= l && j >= r) {
			SEG[p] += x;
			LAZ[p] += x;
			return;
		}
		int m=(l+r)/2;
		add(i,j,x,LAZ[p],p*2+1,l,m);
		add(i,j,x,LAZ[p],p*2+2,m+1,r);
		SEG[p] = min(SEG[p*2+1], SEG[p*2+2]);
		LAZ[p] = 0;
	}
	void set(int i, T x, T lazy, int p, int l, int r) {
		SEG[p] += lazy;
		LAZ[p] += lazy;
		if(i < l || i > r) return;
		if(l == r) {
			SEG[p] = x;
			return;
		}
		int m=(l+r)/2;
		set(i,x,LAZ[p],p*2+1,l,m);
		set(i,x,LAZ[p],p*2+2,m+1,r);
		SEG[p] = min(SEG[p*2+1], SEG[p*2+2]);
		LAZ[p] = 0;
	}
	T getMin(int i, int j, T lazy, int p, int l, int r) {
        if(j < i) return MAX;
		SEG[p] += lazy;
		LAZ[p] += lazy;
		if(j < l || i > r) return MAX;
		if(i <= l && j >= r) return SEG[p];
		int m=(l+r)/2;
		T a=getMin(i,j,LAZ[p],p*2+1,l,m);
		T b=getMin(i,j,LAZ[p],p*2+2,m+1,r);
		return min(a,b);
	}
	inline void add(int i, int j, T x)	{add(i,j,x,0,0,0,size-1);}
	inline void add(int i, T x) 		{add(i,i,x,0,0,0,size-1);}
	inline void set(int i, T x) 		{set(i  ,x,0,0,0,size-1);}
	inline T getMin(int i, int j) 		{return getMin(i,j,0,0,0,size-1);}
	inline T getMin(int i) 				{return getMin(i,i,0,0,0,size-1);}

	vector<T> SEG, LAZ;
	int size;
};

typedef MinSegmentTree<int,1000000000,0> MinSegI;
typedef MinSegmentTree<long long,1000000000000000000,0> MinSegLL;

//===================//
//   begin program   //
//===================//
 
const ll MX = 5e5;
vi pos, col;
bitset<MX> connected;
ll n, m, N;
ll nxtC[MX];
ll dp[MX];
 
ll gd(ll i, ll j) {
    return abs(pos[i] - pos[j]);
}

MinSegLL seg1, seg2;
 
long long min_total_length(std::vector<int> r, std::vector<int> b) {
    n = r.sz, m = b.sz;
    N = n+m;
    {
        ll i=0, j=0;
        while(i != n || j != m) {
            if(j == m || (i != n && r[i] < b[j])) {
                pos.pb(r[i++]);
                col.pb(0);
            } else {
                pos.pb(b[j++]);
                col.pb(1);
            }
        }
    }
 
    dp[0] = 0;
    ll beg = -1, cent=-1, lastCol=-1;
    seg1.resize(N+1);
    seg2.resize(N+1);
    ll totCost = 0;
    REP(i,1,N+1) {
        if(col[i-1] != lastCol) {
            lastCol = col[i-1];
            beg = cent;
            cent = i-1;
            REI(x,beg,cent) seg1.set(x,dp[x]);
            REI(x,beg,cent-1) seg1.add(beg,x,-pos[x]);
            REI(x,beg,cent) seg1.add(x,x,-pos[cent - 1]*x);

            REI(x,beg,cent) seg2.set(x,dp[x]);
            REI(x,beg,cent-1) seg2.add(beg,x,-pos[x]);
            REI(x,beg,cent) seg2.add(x,x,-pos[cent]*x);
            totCost = 0;
        }
        totCost += pos[i-1];
        dp[i] = INF;
        if(beg == -1) continue;

        ll y = i-1;
        dp[i] = min(dp[i], seg1.getMin(max(beg,2*cent-y), cent)+pos[cent - 1] * (2*cent - y - 1)+totCost);
        dp[i] = min(dp[i], seg2.getMin(beg,min(cent,2*cent-y-1))+pos[cent] * (2*cent - y - 1)+totCost);
    }
	return dp[N];
}

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