Submission #236976

#	Time	Username	Problem	Language	Result	Execution time	Memory
236976		kshitij_sodani	Candies (JOI18_candies)	C++17	0 / 100	8 ms	640 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;
	for(llo i=0;i<n;i++){
		ss.insert({-it[i],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;
		llo ind=no.b;
		llo kk=no.a;
		
		if(l[ind]!=-1){
			kk+=it[l[ind]];
		/*	if(ss.find({-it[l[ind]],l[ind]})==ss.end()){
				while(true){
					continue;
				}
			}*/
			ss.erase({-it[l[ind]],l[ind]});
		}
		if(r[ind]!=-1){
			kk+=it[r[ind]];
		/*	if(ss.find({-it[r[ind]],r[ind]})==ss.end()){
				while(true){
					continue;
				}
			}*/
			ss.erase({-it[r[ind]],r[ind]});
		}
		if(l[ind]!=-1 and r[ind]!=-1){
			ss.insert({-kk,ind});
			it[ind]=kk;
		}
		/*cout<<l[ind]<<","<<r[ind]<<endl;
		cout<<it[l[ind]]<<","<<it[ind]<<","<<it[r[ind]]<<endl;
		cout<<l[l[ind]]<<":"<<r[r[ind]]<<endl;
		cout<<kk<<endl;*/
		if(l[ind]!=-1){
			if(l[l[ind]]!=-1){
				r[l[l[ind]]]=ind;
			//	cout<<l[l[ind]]<<"::"<<ind<<endl;
				int x=l[l[ind]];
				l[l[ind]]=-1;
				r[l[ind]]=-1;
				l[ind]=x;
				
			}
			else{
				r[l[ind]]=-1;
				l[l[ind]]=-1;
				l[ind]=-1;

			}
		}
		if(r[ind]!=-1){
			if(r[r[ind]]!=-1){
				l[r[r[ind]]]=ind;
				int x=r[r[ind]];
				l[r[ind]]=-1;
				r[r[ind]]=-1;
				r[ind]=x;

			}
			else{
				r[r[ind]]=-1;
				l[r[ind]]=-1;
				r[ind]=-1;
			}
		}

		
		cout<<su<<endl;
	}

	return 0;
}

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