Submission #253405

#	Time	Username	Problem	Language	Result	Execution time	Memory
253405		lyc	Candies (JOI18_candies)	C++14	100 / 100	650 ms	29048 KiB

candies

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ii=pair<long long,int>;

const int mxN = 2e5+5;

int N;
multiset<ii> ms;
map<int,ii> mp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N;
    FOR(i,1,N){
		int A; cin >> A;
		ms.insert(ii(A,i));
		mp[i] = ii(A,1);
	}
	
	long long ans = 0;
	FOR(_i,1,(N+1)/2){
		//~ cout << _i << ":: "; for (auto& x : ms) { cout << x.first << ' '; } cout << endl;
		auto i = prev(ms.end());
		ans += i->first;
		int idx = i->second;
		auto y = mp.find(idx);
		ii nw = ii(-y->second.first, -y->second.second);
		
		if (y != mp.begin()) {
			auto x = prev(y);
			ms.erase(ii(x->second.first,x->first));
			nw.first += x->second.first;
			nw.second += x->second.second;
			mp.erase(x);
		}
		if (next(y) != mp.end()) {
			auto z = next(y);
			ms.erase(ii(z->second.first,z->first));
			nw.first += z->second.first;
			nw.second += z->second.second;
			mp.erase(z);
		}
		
		ms.erase(i);
		mp.erase(y);
		if (nw.second > 0) ms.insert(ii(nw.first, idx));
		mp[idx] = nw;
		//~ cout << _i << ":: "; for (auto& x : mp) { cout << x.second.first << ' '; } cout << endl;
		cout << ans << '\n';
	}
}

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