oj.uz

Submission #109444

# Submission time Handle Problem Language Result Execution time Memory
109444 2019-05-06T15:02:57 Z njchung99 즐거운 채소 기르기 (JOI14_growing) C++14
100 / 100
 351 ms 16300 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 3 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 284 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 7 ms 640 KB Output is correct
9 Correct 8 ms 640 KB Output is correct
10 Correct 9 ms 640 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 2720 KB Output is correct
2 Correct 144 ms 4968 KB Output is correct
3 Correct 176 ms 7928 KB Output is correct
4 Correct 262 ms 9732 KB Output is correct
5 Correct 178 ms 9592 KB Output is correct
6 Correct 106 ms 4984 KB Output is correct
7 Correct 246 ms 13904 KB Output is correct
8 Correct 261 ms 16048 KB Output is correct
9 Correct 351 ms 16300 KB Output is correct
10 Correct 339 ms 16120 KB Output is correct