Submission #236967

# Submission time Handle Problem Language Result Execution time Memory
236967 2020-06-04T06:36:58 Z kshitij_sodani Candies (JOI18_candies) C++17
0 / 100
8 ms 512 KB
#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]];
			ss.erase({-it[l[ind]],l[ind]});
		}
		if(r[ind]!=-1){
			kk+=it[r[ind]];
			ss.erase({-it[r[ind]],r[ind]});
		}
		ss.insert({-kk,ind});
		/*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{
				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[ind]=-1;
			}
		}
		it[ind]=kk;
		cout<<su<<endl;
	}

	return 0;
}
# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -