Submission #34681

#	Time	Username	Problem	Language	Result	Execution time	Memory
34681		mohammad_kilani	Wiring (IOI17_wiring)	C++14	100 / 100	653 ms	21588 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define red 1
#define blue 0
const int N = 200010;

long long seg[4 * N] , lazy[4 * N] , dp[N];
vector< pair<int,bool> > v;
int n , nxt[N];

long long getmin(int s,int e,int idx,int l,int r){
	if(s > r || e < l) return 1e18;
	if(s >= l && e <= r) return seg[idx] + lazy[idx];
	lazy[idx*2] += lazy[idx];
	lazy[idx*2+1] += lazy[idx];
	seg[idx] += lazy[idx];
	lazy[idx] = 0;
	return min(getmin(s,(s+e)/2,idx*2,l,r),getmin((s+e)/2+1,e,idx*2+1,l,r));
}

long long update(int s,int e,int idx,int l,int r,long long val){
	if(s > r || e < l) return seg[idx] + lazy[idx];
	if(s >= l && e <= r){
		lazy[idx] += val;
		return seg[idx] + lazy[idx];
	}
	lazy[idx*2] += lazy[idx];
	lazy[idx*2+1] += lazy[idx];
	lazy[idx] =0 ;
	return seg[idx] = min(update(s,(s+e)/2,idx*2,l,r,val),update((s+e)/2+1,e,idx*2+1,l,r,val));
}


long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int j =0 ;
	for(int i=0;i<r.size();i++){
		while(j < b.size() && b[j] < r[i]) v.push_back(make_pair(b[j++],blue));
		v.push_back(make_pair(r[i],red));
	}
	while(j < b.size()) v.push_back(make_pair(b[j++],blue));
	n = v.size();
	nxt[n] = n;
	for(int i=n-1;i>=0;i--){
		if(v[i].second != v[i+1].second) nxt[i] = i + 1; else nxt[i] = nxt[i+1];
	}
	for(int i=n-1;i>=0;i--){
		if(nxt[i] == n){
			dp[i] = 1e18;
			update(0,n,1,i,i,dp[i]);
			continue;
		}
		dp[i] = 1e18;
		if(nxt[i] == i + 1){
			long long sum = 0 ;
			for(int j=i+1;j<nxt[i+1];j++){
				update(0,n,1,j,j,-getmin(0,n,1,j,j));
				update(0,n,1,j,j,sum + dp[j]);
				sum += v[j].first - v[i].first;
			}
			for(int j=nxt[i+1];j<=nxt[nxt[i+1]];j++){
				update(0,n,1,j,j,-getmin(0,n,1,j,j));
				update(0,n,1,j,j,dp[j] + sum);
				if(j < nxt[nxt[i+1]]) sum += v[j].first - v[i+1].first;
			}
			dp[i] = min(dp[i],getmin(0,n,1,i+2,nxt[nxt[i+1]]));
			update(0,n-1,1,i,i,dp[i]);
		}
		else{
			int cur = nxt[i] ; 
			int cur2 = nxt[cur] - 1;
			int num = cur - i;
			long long s = 0 ;
			if(cur2 - cur < num){
				if(cur+1 <= cur2) update(0,n,1,cur+1,cur2,v[cur].first - v[i].first);
			}
			else{
				update(0,n,1,cur+1,cur+num-1,v[cur].first-v[i].first);
				if(cur+num <= cur2){
					update(0,n,1,cur+num,cur2,v[cur-1].first - v[i].first);
				}
			}
			cur2++;
			if(cur2 - cur < num) s = v[cur].first - v[i].first;
			else s = v[cur-1].first - v[i].first;
			update(0,n,1,cur2,nxt[cur2],s);
			dp[i] = getmin(0,n,1,cur+1,nxt[cur2]);
			update(0,n,1,i,i,dp[i]);
		}

	}
	return dp[0];

}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<r.size();i++){
               ^
wiring.cpp:38:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < b.size() && b[j] < r[i]) v.push_back(make_pair(b[j++],blue));
           ^
wiring.cpp:41:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(j < b.size()) v.push_back(make_pair(b[j++],blue));
          ^

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