oj.uz

Submission #69934

# Submission time Handle Problem Language Result Execution time Memory
69934 2018-08-22T05:23:12 Z E869120 Wiring (IOI17_wiring) C++14
45 / 100
 1000 ms 20692 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],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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7416 KB Output is correct
2 Correct 9 ms 7596 KB Output is correct
3 Correct 7 ms 7596 KB Output is correct
4 Correct 8 ms 7612 KB Output is correct
5 Correct 9 ms 7612 KB Output is correct
6 Correct 8 ms 7696 KB Output is correct
7 Correct 10 ms 7696 KB Output is correct
8 Correct 8 ms 7696 KB Output is correct
9 Correct 7 ms 7696 KB Output is correct
10 Correct 8 ms 7696 KB Output is correct
11 Correct 8 ms 7696 KB Output is correct
12 Correct 7 ms 7696 KB Output is correct
13 Correct 8 ms 7696 KB Output is correct
14 Correct 12 ms 7696 KB Output is correct
15 Correct 8 ms 7696 KB Output is correct
16 Correct 8 ms 7768 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7768 KB Output is correct
2 Correct 8 ms 7768 KB Output is correct
3 Correct 72 ms 18900 KB Output is correct
4 Correct 74 ms 18900 KB Output is correct
5 Correct 78 ms 18900 KB Output is correct
6 Correct 97 ms 20568 KB Output is correct
7 Correct 102 ms 20624 KB Output is correct
8 Correct 93 ms 20624 KB Output is correct
9 Correct 106 ms 20692 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20692 KB Output is correct
2 Correct 8 ms 20692 KB Output is correct
3 Execution timed out 1070 ms 20692 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20692 KB Output is correct
2 Correct 113 ms 20692 KB Output is correct
3 Correct 583 ms 20692 KB Output is correct
4 Correct 145 ms 20692 KB Output is correct
5 Correct 565 ms 20692 KB Output is correct
6 Correct 10 ms 20692 KB Output is correct
7 Correct 8 ms 20692 KB Output is correct
8 Correct 9 ms 20692 KB Output is correct
9 Correct 9 ms 20692 KB Output is correct
10 Correct 9 ms 20692 KB Output is correct
11 Correct 8 ms 20692 KB Output is correct
12 Correct 8 ms 20692 KB Output is correct
13 Correct 8 ms 20692 KB Output is correct
14 Correct 8 ms 20692 KB Output is correct
15 Correct 11 ms 20692 KB Output is correct
16 Correct 8 ms 20692 KB Output is correct
17 Correct 8 ms 20692 KB Output is correct
18 Correct 107 ms 20692 KB Output is correct
19 Correct 518 ms 20692 KB Output is correct
20 Correct 177 ms 20692 KB Output is correct
21 Correct 109 ms 20692 KB Output is correct
22 Correct 99 ms 20692 KB Output is correct
23 Correct 87 ms 20692 KB Output is correct
24 Correct 88 ms 20692 KB Output is correct

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7416 KB Output is correct
2 Correct 9 ms 7596 KB Output is correct
3 Correct 7 ms 7596 KB Output is correct
4 Correct 8 ms 7612 KB Output is correct
5 Correct 9 ms 7612 KB Output is correct
6 Correct 8 ms 7696 KB Output is correct
7 Correct 10 ms 7696 KB Output is correct
8 Correct 8 ms 7696 KB Output is correct
9 Correct 7 ms 7696 KB Output is correct
10 Correct 8 ms 7696 KB Output is correct
11 Correct 8 ms 7696 KB Output is correct
12 Correct 7 ms 7696 KB Output is correct
13 Correct 8 ms 7696 KB Output is correct
14 Correct 12 ms 7696 KB Output is correct
15 Correct 8 ms 7696 KB Output is correct
16 Correct 8 ms 7768 KB Output is correct
17 Correct 9 ms 7768 KB Output is correct
18 Correct 8 ms 7768 KB Output is correct
19 Correct 72 ms 18900 KB Output is correct
20 Correct 74 ms 18900 KB Output is correct
21 Correct 78 ms 18900 KB Output is correct
22 Correct 97 ms 20568 KB Output is correct
23 Correct 102 ms 20624 KB Output is correct
24 Correct 93 ms 20624 KB Output is correct
25 Correct 106 ms 20692 KB Output is correct
26 Correct 9 ms 20692 KB Output is correct
27 Correct 8 ms 20692 KB Output is correct
28 Execution timed out 1070 ms 20692 KB Time limit exceeded
29 Halted 0 ms 0 KB -