Submission #559084

#	Time	Username	Problem	Language	Result	Execution time	Memory
559084		mosiashvililuka	Wiring (IOI17_wiring)	C++14	100 / 100	68 ms	13860 KiB

wiring

#include<bits/stdc++.h>
#include "wiring.h"
using namespace std;
const long long N=99999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,PPI,pi,cost[200009],fen[200009],fen2[200009],jm[200009],L[200009],R[200009];
pair <long long, long long> PP[200009];
pair <long long, pair <long long, long long> > p[200009];
void cle(long long q){
	q++;
	while(q<=200005){
		fen[q]=N;
		q=q+(q&(-q));
	}
}
void cle2(long long q){
	q++;q=200004-q;
	while(q<=200005){
		fen2[q]=N;
		q=q+(q&(-q));
	}
}
void upd(long long q, long long w){
	q++;
	while(q<=200005){
		fen[q]=min(fen[q],w);
		q=q+(q&(-q));
	}
}
long long read(long long q){
	q++;
	long long sm=N;
	while(q>0){
		sm=min(sm,fen[q]);
		q=q-(q&(-q));
	}
	return sm;
}
void upd2(long long q, long long w){
	q++;q=200004-q;
	while(q<=200005){
		fen2[q]=min(fen2[q],w);
		q=q+(q&(-q));
	}
}
long long read2(long long q){
	q++;q=200004-q;
	long long sm=N;
	while(q>0){
		sm=min(sm,fen2[q]);
		q=q-(q&(-q));
	}
	return sm;
}
long long min_total_length(std::vector<int> Rr, std::vector<int> Bb) {
	a=Rr.size()+Bb.size();
	for(i=0; i<Rr.size(); i++){
		PPI++;PP[PPI]={Rr[i],0};
	}
	for(i=0; i<Bb.size(); i++){
		PPI++;PP[PPI]={Bb[i],1};
	}
	sort(PP+1,PP+PPI+1);
	c=0;PP[0]={-1,-1};
	for(i=1; i<=PPI; i++){
		jm[i]=jm[i-1]+PP[i].first;
	}
	for(i=1; i<=PPI; i++){
		if(PP[i].second!=PP[i-1].second){
			if(c!=0){
				pi++;p[pi]={i-c,{PP[c].first,PP[i-1].first}};
				L[pi]=c;R[pi]=i-1;
			}
			c=i;
		}
	}
	pi++;p[pi]={i-c,{PP[c].first,PP[i-1].first}};
	L[pi]=c;R[pi]=a;
	/*for(i=1; i<=pi; i++){
		cout<<p[i].first<<" "<<p[i].second.first<<" "<<p[i].second.second<<"   "<<L[i]<<" "<<R[i]<<"    "<<jm[R[i]]-jm[L[i]-1]<<"\n";
	}*/
	for(i=0; i<=200007; i++){
		fen[i]=fen2[i]=N;
	}
	//zx=-jm[1];zx+=p[1].second.second*p[1].first;
	zx=-(jm[R[1]]);zx+=p[1].second.second*p[1].first;
	upd(p[1].first,zx);
	//zx=-jm[1];zx+=p[2].second.first*p[1].first;
	zx=-(jm[R[1]]);zx+=p[2].second.first*p[1].first;
	upd2(p[1].first,zx);
	for(i=2; i<=pi; i++){
		for(j=0; j<=p[i].first; j++){
			//zx=jm[i]+read(j)-p[i-1].second.second*j;
			zx=(jm[L[i]+j-1]-jm[L[i]-1])+read(j)-p[i-1].second.second*j;
			cost[j]=zx;
			//zx=jm[i]+read2(j)-p[i].second.first*j;
			zx=(jm[L[i]+j-1]-jm[L[i]-1])+read2(j)-p[i].second.first*j;
			cost[j]=min(cost[j],zx);
		}
		for(j=0; j<=p[i-1].first; j++){
			cle(j);cle2(j);
		}
		/*cout<<i<<" "<<cost[p[i].first]<<"\n";
		cout<<cost[1]<<"\n";*/
		if(i==pi){
			return cost[p[i].first];
		}
		for(j=0; j<=p[i].first; j++){
			//zx=-jm[i]+cost[j];zx+=p[i].second.second*(p[i].first-j);
			zx=-(jm[R[i]]-jm[L[i]+j-1])+cost[j];zx+=p[i].second.second*(p[i].first-j);
			upd(p[i].first-j,zx);
			//zx=-jm[i]+cost[j];zx+=p[i+1].second.first*(p[i].first-j);
			zx=-(jm[R[i]]-jm[L[i]+j-1])+cost[j];zx+=p[i+1].second.first*(p[i].first-j);
			upd2(p[i].first-j,zx);
		}
	}
	return 0;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:56:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(i=0; i<Rr.size(); i++){
      |           ~^~~~~~~~~~
wiring.cpp:59:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(i=0; i<Bb.size(); i++){
      |           ~^~~~~~~~~~

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