oj.uz

Submission #72884

# Submission time Handle Problem Language Result Execution time Memory
72884 2018-08-27T07:27:56 Z Sa1378 Wiring (IOI17_wiring) C++17
0 / 100
 217 ms 17484 KB 
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N ((int)101*1000)
#define INF ((ll)1e17)

ll n,dp[N];
vector <pair<int,bool> > a;
ll seg[4*N],lazy[4*N];

void shift(int id)
{
	seg[id*2]+=lazy[id];
	seg[id*2+1]+=lazy[id];
	lazy[id*2]+=lazy[id];
	lazy[id*2+1]+=lazy[id];
	lazy[id]=0;
}

void update(int ql,int qr,ll val,int xl=0,int xr=n,int id=1)
{
	if(qr<=xl || xr<=ql)return ;
	if(ql<=xl && xr<=qr)
	{
		seg[id]+=val;
		lazy[id]+=val;
		return ;
	}
	int mid=(xl+xr)/2;
	shift(id);
	update(ql,qr,val,xl,mid,id*2);
	update(ql,qr,val,mid,xr,id*2+1);
	seg[id]=min(seg[id*2],seg[id*2+1]);
}

ll query(int ql,int qr,int xl=0,int xr=n,int id=1)
{
	if(qr<=xl || xr<=ql)return INF;
	if(ql<=xl && xr<=qr)return seg[id];
	int mid=(xl+xr)/2;
	shift(id);
	return min(query(ql,qr,xl,mid,id*2),query(ql,qr,mid,xr,id*2+1));
}

ll min_total_length(vector<int> r,vector<int> b)
{
	for(auto u:r)a.push_back({u,0});
	for(auto u:b)a.push_back({u,1});
	sort(a.begin(),a.end());
	n=a.size();
	int i=0;
	while(i<n && a[i].second==a[0].second)i++;
	int l=0,l2=i;
	for(ll j=i-1,sum=0;j>=0;j--)
	{
		sum+=a[i-1].first-a[j].first+(a[i].first-a[i-1].first);
		update(j,j+1,sum+((j>0)?INF:0));
		dp[j]=INF;
	}
	dp[i]=query(l,l2);i++;
	//cout<<i-1<<" "<<dp[i-1]<<"\n";
	for(;i<n;i++)
	{
		if(a[i].second==a[l2].second)
		{
			update(max(l,l2-(i-l2)),l2,a[l2].first-a[l2-1].first);
	//		cout<<query(l,l2)<<"\n";
			update(l,l2,a[i].first-a[l2].first);
			dp[i]=query(l,l2);
	//		cout<<i<<" "<<dp[i]<<"\n";
			continue;
		}
		l=l2;l2=i;
		for(ll j=i-1,sum=0;j>=l;j--)
		{
			sum+=a[i-1].first-a[j].first+(a[i].first-a[i-1].first);
			update(j,j+1,sum+dp[j-1]);
		}
		dp[i]=query(l,l2);
	//	cout<<i<<" "<<dp[i]<<"\n";
	}
	return dp[n-1];
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 456 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14694'
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 564 KB Output is correct
2 Correct 2 ms 564 KB Output is correct
3 Runtime error 71 ms 17404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17404 KB Output is correct
2 Correct 2 ms 17404 KB Output is correct
3 Runtime error 167 ms 17468 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17468 KB Output is correct
2 Runtime error 217 ms 17484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 456 KB 3rd lines differ - on the 1st token, expected: '14340', found: '14694'
3 Halted 0 ms 0 KB -