Submission #58165

#	Time	Username	Problem	Language	Result	Execution time	Memory
58165		khsoo01	Candies (JOI18_candies)	C++11	100 / 100	1171 ms	30524 KiB

candies

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const ll N = 200005, inf = 1e18;

ll n, a[N], par[N];
bool dead[N];

set<pll> val, idx;

ll Find (ll X) {
	if(par[X] == X) return X;
	return par[X] = Find(par[X]);
}

ll Erase (ll X) {
	ll A, B;
	tie(A, B) = *idx.lower_bound(pll(Find(X), -inf));
	idx.erase(pll(A, B));
	val.erase(pll(B, A));
	return B;
}

bool is_first (ll I) {
	auto it = idx.lower_bound(pll(Find(I), -inf));
	return (it == idx.begin());
}

ll next_el (ll I) {
	auto it = idx.lower_bound(pll(Find(I), -inf));
	it++;
	if(it == idx.end()) return 0;
	return (*it).first;
}

int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		par[i] = i;
		val.insert(pll(-a[i], i));
		idx.insert(pll(i, -a[i]));
	}
	ll R = 0;
	for(ll i=1;i<=(n+1)/2;i++) {
		ll A, B, X = 0, F = 0, T;
		tie(A, B) = *val.begin();
		R -= A;
		if(!is_first(B)) {
			X += Erase(B-1);
			par[B] = B-1;
		}
		else F = 1;
		T = next_el(B);
		if(T) {
			X += Erase(T);
			par[T] = B;
		}
		else F = 1;
		val.erase(pll(A, B));
		idx.erase(pll(B, A));
		if(!F) {
			A = X - A;
			B = Find(B);
			val.insert(pll(A, B));
			idx.insert(pll(B, A));
		}
		printf("%lld\n",R);
	}
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
candies.cpp:42: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