Submission #69934

#	Time	Username	Problem	Language	Result	Execution time	Memory
69934		E869120	Wiring (IOI17_wiring)	C++14	45 / 100	1070 ms	20692 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;

long long R[100009], B[100009], SR[100009], SB[100009], r[100009], b[100009], N, M;
vector<int>X[100009],Y[200009];
long long dp[200009],SS[129][200009]; int used[200009];

long long range_red(long long l,long long r){
	return SR[r]-SR[l];
}
long long range_blue(long long l,long long r){
	return SB[r]-SB[l];
}

long long total_sum(long long px, long long py, long long qx, long long qy){
	long long v = py - px + N,tx = px, dif = py - px, sum = 0;
	
	if(used[v] >= 1) return SS[used[v]][qx];
	
	for(int i=0;i<Y[v].size();i++){
		long long E = Y[v][i];if(E > qx) E = qx + 1;
		if(R[tx] > B[tx + dif]) sum += range_red(tx, E) - range_blue(tx + dif, E + dif);
		else sum -= range_red(tx, E) - range_blue(tx + dif, E + dif);
		if(E == qx+1) return sum;
		tx = E;
	}
	long long E = qx + 1;
	if(R[tx]>B[tx+dif]) sum+=range_red(tx,E)-range_blue(tx+dif,E+dif);
	else sum-=range_red(tx,E)-range_blue(tx+dif,E+dif);
	return sum;
}

void init(){
	for(int i=0;i<N;i++){
		int pos1=lower_bound(B,B+M,R[i])-B;
		int minx=(1<<30),minid=-10;
		if(pos1<M){int z=abs(R[i]-B[pos1]);if(z<minx){minx=z;minid=pos1;}}
		if(pos1>0){int z=abs(R[i]-B[pos1-1]);if(z<minx){minx=z;minid=pos1-1;}}
		X[i].push_back(minid);
	}
	for(int i=0;i<M;i++){
		int pos1=lower_bound(R,R+N,B[i])-R;
		int minx=(1<<30),minid=-10;
		if(pos1<N){int z=abs(B[i]-R[pos1]);if(z<minx){minx=z;minid=pos1;}}
		if(pos1>0){int z=abs(B[i]-R[pos1-1]);if(z<minx){minx=z;minid=pos1-1;}}
		X[minid].push_back(i);
	}
	vector<pair<int,int>>G;
	for(int i=0;i<N;i++){G.push_back(make_pair(R[i],0));SR[i+1]=SR[i]+R[i];}
	for(int i=0;i<M;i++){G.push_back(make_pair(B[i],1));SB[i+1]=SB[i]+B[i];}
	sort(G.begin(),G.end());
	Y[N].push_back(0);int sr=0,sb=0;
	for(int i=0;i<G.size();i++){
		if(G[i].second==0) sr++; else sb++;
		Y[sb-sr+N].push_back(sr);
	}
	
	int cnts=0;
	for(int i=0;i<=N+M;i++){
		if(Y[i].size()<1700) continue;
		cnts++;used[i]=cnts;
		long long ex=0,ey=0,sums=0; if(i<N) ex=N-i; if(i>N) ey=i-N;
		while(ex<N && ey<M){sums+=abs(R[ex]-B[ey]);SS[cnts][ex]=sums;ex++;ey++;}
	}
}

long long getval(long long cx,long long cy){
	if(cx<=0 || cy<=0) return (1LL<<60);
	long long E1 = cy - cx + N;
	long long ex = 0, ey = 0; if(cx > cy) ex = cx - cy; if(cx < cy) ey = cy - cx;
	long long vx = total_sum(ex, ey, cx - 1, cy - 1) + dp[E1];
	return vx;
}
void writeval(long long cx,long long cy,long long t){
	long long E1 = cy - cx + N;
	long long ex = 0, ey = 0; if(cx > cy) ex = cx - cy; if(cx < cy) ey = cy - cx;
	long long F = total_sum(ex, ey, cx - 1, cy - 1);
	dp[E1] = min(dp[E1], t - F);
}

long long min_total_length(vector<int> r, vector<int> b) {
	// -------------------------- 第一部：前準備 --------------------------
	N = r.size(); for(int i=0;i<N;i++) R[i] = r[i];
	M = b.size(); for(int i=0;i<M;i++) B[i] = b[i];
	
	init();
	//for(int i=0;i<N;i++) cout<<i<<" "<<total_sum(0,0,i,i)<<endl;
	
	for(int i=0;i<=N+M;i++) dp[i] = (1LL<<60);
	for(int i=0;i<N;i++) sort(X[i].begin(),X[i].end());
	
	dp[N]=0;
	for(int i=0;i<N;i++){
		for(int j=0;j<(int)X[i].size();j++){
			long long v0 = getval(i+1,X[i][j]+1);
			long long v1 = getval(i+1,X[i][j]); if(v1!=(1LL<<60))v1+=abs(R[i]-B[X[i][j]]);
			long long v2 = getval(i, X[i][j]+1); if(v2!=(1LL<<60))v2+=abs(R[i]-B[X[i][j]]);
			writeval(i+1,X[i][j]+1,min({v0,v1,v2}));
			//cout<<i<<" "<<X[i][j]<<" "<<v0<<" "<<v1<<" "<<v2<<endl;
		}
		//for(int i=0;i<=N+M;i++) cout<<i<<":"<<dp[i]<<endl;
	}
	return getval(N, M);
}

/*int main(){
	int n,m;cin>>n>>m;
	vector<int>vec1,vec2;
	for(int i=0;i<n;i++){int p;cin>>p;vec1.push_back(p);}
	for(int i=0;i<m;i++){int p;cin>>p;vec2.push_back(p);}
	
	cout<<min_total_length(vec1,vec2)<<endl;
	return 0;
}*/

Compilation message (stderr)

wiring.cpp: In function 'long long int total_sum(long long int, long long int, long long int, long long int)':
wiring.cpp:21:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<Y[v].size();i++){
              ~^~~~~~~~~~~~
wiring.cpp: In function 'void init()':
wiring.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<G.size();i++){
              ~^~~~~~~~~

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