oj.uz

Submission #69933

# Submission time Handle Problem Language Result Execution time Memory
69933 2018-08-22T05:14:54 Z E869120 Wiring (IOI17_wiring) C++14
45 / 100
 1000 ms 31336 KB 
#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];

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;
	
	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);
	}
}

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

wiring.cpp: In function 'long long int total_sum(long long int, long long int, long long int, long long int)':
wiring.cpp:19: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:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<G.size();i++){
              ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7368 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 9 ms 7496 KB Output is correct
4 Correct 7 ms 7496 KB Output is correct
5 Correct 8 ms 7624 KB Output is correct
6 Correct 8 ms 7624 KB Output is correct
7 Correct 9 ms 7624 KB Output is correct
8 Correct 9 ms 7624 KB Output is correct
9 Correct 8 ms 7624 KB Output is correct
10 Correct 9 ms 7624 KB Output is correct
11 Correct 9 ms 7624 KB Output is correct
12 Correct 7 ms 7680 KB Output is correct
13 Correct 8 ms 7680 KB Output is correct
14 Correct 9 ms 7680 KB Output is correct
15 Correct 9 ms 7680 KB Output is correct
16 Correct 9 ms 7804 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7804 KB Output is correct
2 Correct 8 ms 7804 KB Output is correct
3 Correct 82 ms 18796 KB Output is correct
4 Correct 72 ms 20208 KB Output is correct
5 Correct 74 ms 20380 KB Output is correct
6 Correct 103 ms 25372 KB Output is correct
7 Correct 111 ms 27348 KB Output is correct
8 Correct 108 ms 29304 KB Output is correct
9 Correct 100 ms 31336 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31336 KB Output is correct
2 Correct 10 ms 31336 KB Output is correct
3 Execution timed out 1055 ms 31336 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31336 KB Output is correct
2 Correct 107 ms 31336 KB Output is correct
3 Correct 579 ms 31336 KB Output is correct
4 Correct 197 ms 31336 KB Output is correct
5 Correct 534 ms 31336 KB Output is correct
6 Correct 8 ms 31336 KB Output is correct
7 Correct 8 ms 31336 KB Output is correct
8 Correct 8 ms 31336 KB Output is correct
9 Correct 8 ms 31336 KB Output is correct
10 Correct 9 ms 31336 KB Output is correct
11 Correct 9 ms 31336 KB Output is correct
12 Correct 10 ms 31336 KB Output is correct
13 Correct 9 ms 31336 KB Output is correct
14 Correct 9 ms 31336 KB Output is correct
15 Correct 9 ms 31336 KB Output is correct
16 Correct 9 ms 31336 KB Output is correct
17 Correct 9 ms 31336 KB Output is correct
18 Correct 123 ms 31336 KB Output is correct
19 Correct 709 ms 31336 KB Output is correct
20 Correct 157 ms 31336 KB Output is correct
21 Correct 110 ms 31336 KB Output is correct
22 Correct 99 ms 31336 KB Output is correct
23 Correct 90 ms 31336 KB Output is correct
24 Correct 90 ms 31336 KB Output is correct

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7368 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 9 ms 7496 KB Output is correct
4 Correct 7 ms 7496 KB Output is correct
5 Correct 8 ms 7624 KB Output is correct
6 Correct 8 ms 7624 KB Output is correct
7 Correct 9 ms 7624 KB Output is correct
8 Correct 9 ms 7624 KB Output is correct
9 Correct 8 ms 7624 KB Output is correct
10 Correct 9 ms 7624 KB Output is correct
11 Correct 9 ms 7624 KB Output is correct
12 Correct 7 ms 7680 KB Output is correct
13 Correct 8 ms 7680 KB Output is correct
14 Correct 9 ms 7680 KB Output is correct
15 Correct 9 ms 7680 KB Output is correct
16 Correct 9 ms 7804 KB Output is correct
17 Correct 8 ms 7804 KB Output is correct
18 Correct 8 ms 7804 KB Output is correct
19 Correct 82 ms 18796 KB Output is correct
20 Correct 72 ms 20208 KB Output is correct
21 Correct 74 ms 20380 KB Output is correct
22 Correct 103 ms 25372 KB Output is correct
23 Correct 111 ms 27348 KB Output is correct
24 Correct 108 ms 29304 KB Output is correct
25 Correct 100 ms 31336 KB Output is correct
26 Correct 7 ms 31336 KB Output is correct
27 Correct 10 ms 31336 KB Output is correct
28 Execution timed out 1055 ms 31336 KB Time limit exceeded
29 Halted 0 ms 0 KB -