Submission #109444

#	Time	Username	Problem	Language	Result	Execution time	Memory
109444		njchung99	즐거운 채소 기르기 (JOI14_growing)	C++14	100 / 100	351 ms	16300 KiB

growing

#include<cstdio>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
pair<ll,ll> a[300010];
ll seg[1200000];
ll n;
ll update(ll pos, ll val, ll node, ll x, ll y) {
	if (pos < x || y < pos)return seg[node];
	if (x == y)return seg[node] += val;
	ll mid = (x + y) / 2;
	return seg[node] = update(pos, val, node * 2, x, mid) + update(pos, val, node * 2 + 1, mid + 1, y);
}
ll query(ll lo, ll hi, ll node, ll x, ll y) {
	if (hi < x || y < lo)return 0;
	if (lo <= x && y <= hi)return seg[node];
	ll mid = (x + y) / 2;
	return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * 2 + 1, mid + 1, y);
}
ll getmi(ll idx) {
	ll gap = idx-query(0, idx, 1, 0, n-1);
	ll gap1 = n-1-idx-query(idx, n - 1, 1, 0, n - 1);
	return min(gap, gap1);
}
int main()
{
	scanf("%lld", &n);
	for (ll i = 0; i < n; i++)
	{
		scanf("%lld", &a[i].first);
		a[i].second = i;
	}
	sort(a, a + n);
	ll dap = 0;
	for (ll i = 0; i < n;)
	{
		ll l = i;
		ll r = i+1;
		while (1) {
			if (a[l].first == a[r].first)r++;
			else break;
		}
		r--;
		i = r + 1;
		while (l <= r) {
			ll ax = getmi(a[l].second);
			ll ay = getmi(a[r].second);
			if (ax > ay) {
				dap += ay;
				update(a[r].second, 1, 1, 0, n - 1);
				r--;
			}
			else
			{
				dap += ax;
				update(a[l].second, 1, 1, 0, n - 1);
				l++;
			}
		}
	}
	printf("%lld\n", dap);
}

Compilation message (stderr)

growing.cpp: In function 'int main()':
growing.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
growing.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i].first);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 55 / 55