Submission #73760

#	Time	Username	Problem	Language	Result	Execution time	Memory
73760		TadijaSebez	Candies (JOI18_candies)	C++11	100 / 100	930 ms	28168 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
struct Group
{
	ll val;
	pair<int,int> seg;
	Group(){}
	Group(ll a, int b, int c){ val=a;seg=mp(b,c);}
	Group(ll a, pair<int,int> b){ val=a;seg=b;}
	bool operator < (Group b) const { return val>b.val || val==b.val && seg<b.seg;}
};
set<Group> best;
set<pair<int,int> > ord;
set<pair<int,int> >::iterator it;
const int N=400050;
int a[N],n;
ll sum[N];
ll get(pair<int,int> p){ return sum[p.second]+(p.first>0?sum[p.first-1]:0);}
void Del(pair<int,int> p)
{
	//printf("Del: (%i %i)\n",p.first,p.second);
	if(p.first>=1 && p.second<=n) best.erase(Group(get(p),p));
	ord.erase(p);
}
void Ins(pair<int,int> p)
{
	//printf("Ins: (%i %i)\n",p.first,p.second);
	if(p.first>=1 && p.second<=n) best.insert(Group(get(p),p));
	if(p.first>=1 || p.second<=n) ord.insert(p);
}
void Debug()
{
	set<Group>::iterator it;
	for(it=best.begin();it!=best.end();it++)
	{
		printf("%lld:(%i %i) ",it->val,it->seg.first,it->seg.second);
	}
	printf("\n");
}
int main()
{
	int i;
	scanf("%i",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%i",&a[i]);
		sum[i]=-sum[i-1]+a[i];
		ord.insert(mp(i,i));
		best.insert(Group(a[i],i,i));
	}
	for(i=n+1;i<=n*2;i++) sum[i]=-sum[i-1];
	ll sol=0;int cnt=0;
	while(best.size())
	{
		//Debug();
		Group tmp=*best.begin();
		//best.erase(tmp);
		sol+=tmp.val;
		it=ord.find(tmp.seg);
		pair<int,int> dl=*it;
		//printf("%i %i\n",tmp.seg.first,tmp.seg.second);
		tmp.seg.first--;
		tmp.seg.second++;
		pair<int,int> p;
		if(it!=ord.begin())
		{
			it--;p=*it;it++;
			//printf("Left: (%i %i)\n",p.first,p.second);
			if(p.second==tmp.seg.first)
			{
				Del(p);
				//best.erase(Group(get(p),p));
				//ord.erase(p);
				tmp.seg.first=p.first;
			}
		}
		it++;
		if(it!=ord.end())
		{
			p=*it;
			//printf("Right: (%i %i)\n",p.first,p.second);
			if(p.first==tmp.seg.second)
			{
				Del(p);
				//best.erase(Group(get(p),p));
				//ord.erase(p);
				tmp.seg.second=p.second;
			}
		}
		it--;
		Del(dl);
		//ord.erase(*it);
		Ins(tmp.seg);
		//if(tmp.seg.first>=1 || tmp.seg.second<=n)
		//{
		//	if(tmp.seg.first>=1 && tmp.seg.second<=n) best.insert(Group(get(tmp.seg),tmp.seg));
		//	ord.insert(tmp.seg);
		//}
		cnt++;//printf("%i ",cnt);
		printf("%lld\n",sol);
		//if(cnt==(n+1)/2) break;
	}
	return 0;
}

Compilation message (stderr)

candies.cpp: In member function 'bool Group::operator<(Group) const':
candies.cpp:13:67: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  bool operator < (Group b) const { return val>b.val || val==b.val && seg<b.seg;}
                                                        ~~~~~~~~~~~^~~~~~~~~~~~
candies.cpp: In function 'int main()':
candies.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
candies.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&a[i]);
   ~~~~~^~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92