Submission #676464

#	Time	Username	Problem	Language	Result	Execution time	Memory
676464		penguin133	Candies (JOI18_candies)	C++17	100 / 100	245 ms	24140 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define int long long
multiset<pair<int, pair<int, int> > >s;
multiset<pair<int, pair<int, int> > >:: iterator it;
int A[200005], p[200005];
pair<int, pair<int, int> >r[200005];
int px(int x){
	if(p[x] == x)return p[x];
	else return p[x] = px(p[x]);
}
void merge(int a, int b, int c){
	a = px(a), b = px(b), c = px(c);
	if(a != b){
		p[c] = p[b] = a;
		r[a].first += r[c].first - r[b].first;
		r[a].second.first = min({r[a].second.first, r[b].second.first, r[c].second.first});
		r[a].second.second = max({r[c].second.second, r[a].second.second, r[b].second.second});
	}
}
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int ans = 0;
	int n;cin >> n;
	r[0].first = -1e15;
	r[0].second.first = n + 1;
	for(int i=1;i<=n;i++)cin >> A[i], s.insert(make_pair(A[i], make_pair(i,i))), p[i] = i, r[i].first = A[i], r[i].second.first = r[i].second.second = i;
	for(int i=1;i<=(n+1)/2;i++){
		it = --s.end();
		int x = it->first;
		int y = it->second.first;
		int z = it->second.second;
		while(!s.empty() && (r[px(y)].second.first != y || r[px(y)].second.second != z)){
			s.erase(it);
			it = --s.end();
			x = it->first;
			y = it->second.first;
			z = it->second.second;
		}
		ans += x;
		merge(y-1,y,z+1);
		s.insert(r[px(y)]);
		cout << ans << '\n';
	}
}

Compilation message (stderr)

candies.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main(){
      | ^~~~

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