Submission #2172899

---

Source Code Expand

#include<cstdio>
#include<utility>
#include<set>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
long long arr[100002];
int l[100002],r[100002],n;
set<pair<int,int> > se;
inline void del(const int& a)
{
	set<pair<int,int> >::iterator it;
	int b=l[a],c=r[a];
	r[b]=c;
	l[c]=b;
	if(b>0)
	{
		it=se.find(make_pair(a-b,b));
		if(it!=se.end())
		{
			se.erase(it);
		}
	}
	if(c<=n)
	{
		it=se.find(make_pair(c-a,a));
		if(it!=se.end())
		{
			se.erase(it);
		}	
	}
	if(b>0 && c<=n && (arr[b]>0)^(arr[c]>0))
	{
		se.insert(make_pair(c-b,b));
	}
	return;
}
int main()
{
	int i,a,b,dis;
	long long x,ans,remain,rein;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
	{
		scanf("%lld",&arr[i]);
	}
	remain=0;
	se.clear();
	for(i=1;i<=n;++i)
	{
		scanf("%lld",&x);
		arr[i]-=x;
		if(arr[i]<0)
		{
			remain-=arr[i];
		}
	}
	for(i=1;i<=n;++i)
	{
		l[i]=i-1;
		r[i]=i+1;
		if( ((arr[i]>0)^(arr[i+1]>0)) && i<n)
		{
			se.insert(make_pair(1,i));
		}
	}
	ans=0;
	while(remain)
	{
//		printf("%lld %d\n",remain,se.size());
		dis=(se.begin())->first;
		a=(se.begin())->second;
		se.erase(se.begin());
		b=r[a];
		rein=min(abs(arr[a]),abs(arr[b]),remain);
		remain-=rein;
//		printf("rein:%lld\n",rein);
		ans+=dis*rein;
		arr[a]+=(arr[a]>0?-rein:rein);
		arr[b]+=(arr[b]>0?-rein:rein);
		if(arr[a]==0)
		{
			del(a);
		}
		if(arr[b]==0)
		{
			del(b);
		}
	}
	printf("%lld\n",ans);
	return 0;
}
/*
2
1 5
3 1

2
*/
/*
5
1 2 3 4 5
3 3 1 1 1

6
*/
/*
27
46 3 4 2 10 2 5 2 6 7 20 13 9 49 3 8 4 3 19 9 3 5 4 13 9 5 7
10 2 5 6 2 6 3 2 2 5 3 11 13 2 2 7 7 3 9 5 13 4 17 2 2 2 4

48
*/
/*
18
3878348 423911 8031742 1035156 24256 10344593 19379 3867285 4481365 1475384 1959412 1383457 164869 4633165 6674637 9732852 10459147 2810788
1236501 770807 4003004 131688 1965412 266841 3980782 565060 816313 192940 541896 250801 217586 3806049 1220252 1161079 31168 2008961

6302172
*/
/*
2
1 99999999999
1234567891 1

1234567890
*/

Submission Info

Compile Error

In file included from /usr/include/c++/5/bits/stl_tree.h:63:0,
                 from /usr/include/c++/5/set:60,
                 from ./Main.cpp:3:
/usr/include/c++/5/bits/stl_algobase.h: In instantiation of ‘constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare) [with _Tp = long long int; _Compare = long long int]’:
./Main.cpp:76:42:   required from here
/usr/include/c++/5/bits/stl_algobase.h:246:17: error: ‘__comp’ cannot be used as a function
       if (__comp(__b, __a))
                 ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:43:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:46:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&arr[i]);
                        ^
./Main.cpp:52:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attr...