Submission #132995

#	Time	Username	Problem	Language	Result	Execution time	Memory
132995		mirbek01	Candies (JOI18_candies)	C++11	100 / 100	1271 ms	29840 KiB

candies

# include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 3;

int n, a[N];
long long ans;
set < pair<long long, long long> > val, ind;

int main(){
	cin >> n;
	
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		val.insert( {a[i], i} );
		ind.insert( {i, a[i]} );
	}
	
	val.insert({-1e18, -1}), ind.insert({-1, -1e18});
	val.insert({-1e18, n + 1}), ind.insert({n + 1, -1e18});
	
	for(int i = 1; i <= (n + 1) / 2; i ++){
		auto it = -- val.end();
		ans += it->first;
		auto ps = ind.find({it->second, it->first});
		auto x = *prev(ps);
		auto y = *ps;
		auto z = *next(ps);
		for(auto it : {x, y, z}){
			ind.erase(it);
			val.erase({it.second, it.first});
		}
		ind.insert({y.first, x.second + z.second - y.second});
		val.insert({x.second + z.second - y.second, y.first});
		cout << ans << endl;
	}
}

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