oj.uz

Submission #236978

# Submission time Handle Problem Language Result Execution time Memory
236978 2020-06-04T07:22:55 Z kshitij_sodani Candies (JOI18_candies) C++17
0 / 100
 9 ms 768 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;
	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.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 640 KB Output is correct
2 Correct 9 ms 640 KB Output is correct
3 Correct 9 ms 768 KB Output is correct
4 Correct 8 ms 640 KB Output is correct
5 Correct 8 ms 768 KB Output is correct
6 Correct 8 ms 640 KB Output is correct
7 Incorrect 9 ms 768 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 640 KB Output is correct
2 Correct 9 ms 640 KB Output is correct
3 Correct 9 ms 768 KB Output is correct
4 Correct 8 ms 640 KB Output is correct
5 Correct 8 ms 768 KB Output is correct
6 Correct 8 ms 640 KB Output is correct
7 Incorrect 9 ms 768 KB Output isn't correct
8 Halted 0 ms 0 KB -