oj.uz

Submission #58166

# Submission time Handle Problem Language Result Execution time Memory
58166 2018-07-17T04:59:58 Z 윤교준(#1690) Candies (JOI18_candies) C++11
0 / 100
 6 ms 632 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

const int MAXN = 200005;

set<pli> PQ;
set<pil> CH;

ll A[MAXN];

ll Ans;
int N;

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i <= N; i++) cin >> A[i];
	
	for(int i = 1; i <= N; i++) {
		PQ.insert(pli(A[i], i));
		CH.insert(pil(i, A[i]));
	}
	
	for(int tc = 1; tc <= (N+1)/2; tc++) {
		ll dst; int idx;
		{
			auto it = prev(PQ.end());
			tie(dst, idx) = *it;
		}

		Ans += dst;

		ll a = -INF, b = dst, c = -INF;
		int ai = -1, bi = idx, ci = -1;
		{
			auto it = CH.lower_bound(pil(idx, dst));

			{
				if(CH.begin() != it) {
					auto bt = prev(it);
					tie(ai, a) = *bt;
				}
			}
			{
				auto bt = next(it);
				if(CH.end() != bt) {
					tie(ci, c) = *bt;
				}
			}
		}

		if(0 < ai) CH.erase(pil(ai, a));
		if(0 < bi) CH.erase(pil(bi, b));
		if(0 < ci) CH.erase(pil(ci, c));

		if(0 < ai) PQ.erase(pli(a, ai));
		if(0 < bi) PQ.erase(pli(b, bi));
		if(0 < ci) PQ.erase(pli(c, ci));


		CH.insert(pil(bi, a+c-b));
		PQ.insert(pli(a+c-b, bi));

		printf("%lld\n", Ans);
	}

	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -