Submission #236376

#	Time	Username	Problem	Language	Result	Execution time	Memory
236376		MvC	Candies (JOI18_candies)	C++11	100 / 100	968 ms	40184 KiB

candies

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2e5+50;
const ll mod=1e9+7;
using namespace std;
int n,i,j,l,r;
pair<int,int>pr;
set<pair<ll,pair<int,int> > >sv;
set<pair<ll,pair<int,int> > >::iterator iv;
set<pair<int,int> >si;
set<pair<int,int> >::iterator ii;
vector<pair<int,int> >vc;
map<pair<int,int>,ll>mp;
ll rs,cur,a[nmax];
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<=n;i++)
	{
		sv.in(mkp(a[i],mkp(i,i)));
		si.in(mkp(i,i));
		mp[mkp(i,i)]=a[i];
	}
	for(i=1;i<=(n+1)/2;i++)
	{
		iv=(--sv.end());
		rs+=iv->fr;
		pr=iv->sc;
		ii=si.fd(pr);
		vc.clear();
		if(ii!=si.begin())
		{
			ii--;
			vc.pb(*ii);
			ii++;
		}
		vc.pb(*ii);
		ii++;
		if(ii!=si.end())vc.pb(*ii);
		cur=0,l=inf,r=0;
		for(j=0;j<(int)vc.size();j++)
		{
			l=min(l,vc[j].fr);
			r=max(r,vc[j].sc);
			if(vc[j]!=pr)cur+=mp[vc[j]];
			else cur-=mp[vc[j]];
			si.er(si.fd(vc[j]));
			sv.er(sv.fd(mkp(mp[vc[j]],vc[j])));
		}
		if((int)vc.size()==3)
		{
			mp[mkp(l,r)]=cur;
			si.in(mkp(l,r));
			sv.in(mkp(cur,mkp(l,r)));
		}
		cout<<rs<<'\n';
	}
	return 0;
}

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