Submission #1062772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062772		Malix	Wiring (IOI17_wiring)	C++14	13 / 100	35 ms	2768 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))
 
ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	int n=r.size();
	int m=b.size();
if(r.back()<b[0]){
	stack<int> ar,br;
	REP(i,0,n)ar.push(r[i]);
	REP(i,0,m)br.push(b[i]);
	ll ans=0;
	int x=r.back(),y=b[0];
	while(!ar.empty()||!br.empty()){
		int l=x,r=y;
		if(!ar.empty()){
			l=ar.top();
			ar.pop();
		}
		if(!br.empty()){
			r=br.top();
			br.pop();
		}
		ans+=(ll)r-l;
	}
	return ans;
}
	priority_queue<pi> pq;
	REP(i,0,n)pq.push({r[i],0});
	REP(i,0,m)pq.push({b[i],1});
	ll k=1,t=pq.top().S;pq.pop();
	vector<ll> arr;
	while(!pq.empty()){
		int y=pq.top().S;
		pq.pop();
		if(t==y)k++;
		else{
			arr.PB(k);
			k=1;
			t=y;
		}
	}
	arr.PB(k);
	int s=arr.size();cerr<<s<<"\n";
	vector<ll> brr(s,0);
	ll ans=0;
	REP(i,0,s-1){
		if(arr[i]==0)continue;
		ll mn=min(arr[i],arr[i+1]);
		arr[i]-=mn;arr[i+1]-=mn;
		brr[i]=mn;
		ans+=mn*mn;
	}
	if(arr[0]!=0){
		ll p=brr[0]+arr[0];
		ans+=(p*(p+1))/2;
		ans-=(arr[0]*(arr[0]+1))/2;
	}
	REP(i,1,s){
		if(arr[i]==0)continue;
		ll z=abs(brr[i]-brr[i-1]);
		if(z>=arr[i]){
			ll q=min(brr[i],brr[i-1]);
			ll p=q+arr[i];
			ans+=(p*(p+1))/2;
			ans-=(q*(q+1))/2;
		}
		else{
			ll q=min(brr[i],brr[i-1]);
			ll p=q+z;
			ans+=(p*(p+1))/2;
			ans-=(q*(q+1))/2;
			arr[i]-=z;
			ll tmp=p+arr[i]/2;
			ll ta=(tmp*(tmp+1))/2-(p*(p+1))/2;
			ans+=ta*2;
			if(arr[i]%2==1){
				ll tmp2=tmp+1;
				ans+=(tmp*(tmp+1))/2-(tmp2*(tmp2+1))/2;
			}
		}
	}
	return ans;
}

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