Submission #1158191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158191		pacman	Candies (JOI18_candies)	C++20	8 / 100	5093 ms	23924 KiB

candies

#include <bits/stdc++.h>
#define int long long int

using namespace std;

const int maxn = 2e5 + 100;

int n, a[maxn], ans = 0;
set<pair<int ,int>> s;
set<int> active;


void in(){
	cin >> n;
	for(int i = 0 ;i < n; i++){
		cin >> a[i];
		s.insert(make_pair(a[i], i));
		active.insert(i);
	}
}


void Engine(){
	while(active.size() > 0){
		pair<int ,int> v = *s.rbegin();
		s.erase(v);
		ans += v.first;
		cout << ans << "\n";
		if(active.size() == 1){
			break;
		}
		if(v.second == (*active.begin())){
			active.erase(*active.begin());
			s.erase(make_pair(a[*active.begin()], *active.begin()));
			active.erase(*active.begin());
			continue;
		}
		if(v.second == (*active.rbegin())){
			active.erase(*active.rbegin());
			s.erase(make_pair(a[*active.rbegin()], *active.rbegin()));
			active.erase(*active.rbegin());
			continue;
		}
		active.erase(v.second);
		auto ind = lower_bound(active.begin(), active.end(), v.second);
		auto nxt = ind;
		auto pre = prev(ind);
		active.erase(nxt), active.erase(pre);
		s.erase(make_pair(a[*nxt], *nxt));
		s.erase(make_pair(a[*pre], *pre));
		a[v.second] = a[*pre] + a[*nxt] - a[v.second];
		s.insert(make_pair(a[v.second], v.second));
		active.insert(v.second);
	}
}


int32_t main(){

	ios::sync_with_stdio(0) ,cout.tie(0) ,cin.tie(0);

	in();
	Engine();

	return 0;
}

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