Submission #236978

#	Time	Username	Problem	Language	Result	Execution time	Memory
236978		kshitij_sodani	Candies (JOI18_candies)	C++17	0 / 100	9 ms	768 KiB

candies

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo n;
llo it[200001];
llo l[200001];
llo r[200001];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	for(llo i=0;i<n-1;i++){
		r[i]=i+1;
	}
	r[n-1]=-1;
	l[0]=-1;
	for(llo i=1;i<n;i++){
		l[i]=i-1;
	}
	set<pair<llo,llo>> ss;
	set<llo> aa;
	for(llo i=0;i<n;i++){
		ss.insert({-it[i],i});
		aa.insert(i);
	}
	llo su=0;
	for(llo i=0;i<(n+1)/2;i++){
		pair<llo,llo> no=*(ss.begin());
		ss.erase(no);

		su+=-no.a;
		cout<<su<<endl;
		llo ind=no.b;
		llo su2=no.a;
		auto kk=aa.upper_bound(ind);
		auto ll=aa.lower_bound(ind);
	//	ll--;
		if(kk!=aa.end() and ll!=aa.begin()){
			ll--;
		//	cout<<(*kk)<<","<<(*ll)<<endl;
			su2+=it[*kk];
			su2+=it[*ll];
		//	cout<<su2<<endl;
			it[ind]=su2;
		/*	if(ss.find({-it[*kk],*kk})==ss.end() or ss.find({-it[*ll],*ll})==ss.end()){
				cout<<11<<endl;
				cout<<it[*kk]<<"::"<<it[*ll]<<endl;
			}*/
				ss.erase({-it[*kk],*kk});
				aa.erase(*kk);
				ss.erase({-it[*ll],*ll});
				aa.erase(*ll);
			ss.insert({-su2,ind});
		}
		else{
			aa.erase(ind);
			if(kk!=aa.end()){
				ss.erase({-it[*kk],*kk});
				aa.erase(*kk);
			}
			if(ll!=aa.begin()){
				ll--;
				ss.erase({-it[*ll],*ll});
				aa.erase(*ll);
			}
		}
		/*for(auto j:ss){
			cout<<j.a<<"/"<<j.b<<endl;
		}
		cout<<endl;*/

	}


	return 0;
}

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