Submission #43994

#	Time	Username	Problem	Language	Result	Execution time	Memory
43994		zscoder	Candies (JOI18_candies)	C++17	100 / 100	1135 ms	47556 KiB

candies

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

ll a[211111];
int n;
map<ii, ll> ma;
set<ii> intervals;
ll res[211111];

void solve_fast()
{
	ma.clear(); intervals.clear();
	multiset<pair<ll,ii> > pq;
	for(int i=0;i<n;i++)
	{
		pq.insert(mp(a[i], mp(i,i)));
		intervals.insert(mp(i,i));
		ma[mp(i,i)] = a[i];
	}
	ll ans = 0;
	for(int i=0;i<(n+1)/2;i++)
	{
		while(intervals.find((*prev(pq.end())).se)==intervals.end()) pq.erase(prev(pq.end()));
		ans += (*prev(pq.end())).fi;
		res[i+1] = ans;
		int l = (*prev(pq.end())).se.fi; int r = (*prev(pq.end())).se.se;
		auto it = intervals.find(mp(l,r));
		auto itr = it; auto itl= it;
		itr++; itl--; 
		vector<ii> era;
		if(it!=intervals.begin()) era.pb((*itl));
		if(itr!=intervals.end()) era.pb((*itr));
		if(itr!=intervals.end()&&it!=intervals.begin())
		{
			int veryl = (*itl).fi;
			int veryr = (*itr).se;
			intervals.insert(mp(veryl,veryr));
			ll V = ma[(*itl)] + ma[(*itr)] - ma[mp(l,r)];
			ma[mp(veryl,veryr)] = V;
			pq.insert(mp(V, mp(veryl, veryr)));
		}
		intervals.erase(mp(l,r));
		for(ii x:era) 
		{
			intervals.erase(x);
		}
	}
	for(int i=1;i<=(n+1)/2;i++) cout<<res[i]<<'\n';
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	solve_fast();
}

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