Submission #61587

#	Time	Username	Problem	Language	Result	Execution time	Memory
61587		kingpig9	Candies (JOI18_candies)	C++11	100 / 100	750 ms	27056 KiB

candies

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5 + 10;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

struct union_find {
	int par[MAXN];
	int sz[MAXN];
	int lt[MAXN];
	int rt[MAXN];
	ll inc[MAXN];

	union_find() {
		for (int i = 0; i < MAXN; i++) {
			par[i] = i;
			sz[i] = 1;
			lt[i] = i;
			rt[i] = i;
		}
	}

	int find (int x) {
		return x == par[x] ? x : par[x] = find(par[x]);
	}

	void merge (int x, int y) {
		x = find(x);
		y = find(y);
		assert(x != y);
		par[x] = y;
		sz[y] += sz[x];
		lt[y] = min(lt[x], lt[y]);
		rt[y] = max(rt[x], rt[y]);
	}
};

int N;
ll A[MAXN];
union_find uf = union_find();
set<pair<ll, int>> st;

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%lld", &A[i]);
		uf.inc[i] = A[i];
		st.insert(make_pair(uf.inc[i], i));
	}

	ll ans = 0;
	for (int i = 1; ; i++) {
		auto p = *st.rbegin();
		st.erase(--st.end());
		int ccomp = uf.find(p.se);
		ans += p.fi;
		printf("%lld\n", ans);
		if (i == (N + 1) / 2) {
			break;
		}

		int ltcomp = uf.find(uf.lt[ccomp] - 1);
		int rtcomp = uf.find(uf.rt[ccomp] + 1);
		ll ninc = uf.inc[ltcomp] + uf.inc[rtcomp] - uf.inc[ccomp];
		//erase left
		if (ltcomp != 0) {
			st.erase(make_pair(uf.inc[ltcomp], ltcomp));
		}

		//erase right
		if (rtcomp != N + 1) {
			st.erase(make_pair(uf.inc[rtcomp], rtcomp));
		}

		//ok unite the sides - left & right.
		//EVEN IF THE LEFT IS THE ZERO. THIS WAY YOU WILL NEVER SELECT THIS AGAIN.
		uf.merge(ltcomp, ccomp);
		uf.merge(ccomp, rtcomp);

		ccomp = uf.find(ccomp);
		if (uf.lt[ccomp] != 0 && uf.rt[ccomp] != N + 1) {
			uf.inc[ccomp] = ninc;
			st.insert(make_pair(ninc, ccomp));
		}
	}
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
candies.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &A[i]);
   ~~~~~^~~~~~~~~~~~~~~

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