Submission #39507

#	Time	Username	Problem	Language	Result	Execution time	Memory
39507		14kg	즐거운 채소 기르기 (JOI14_growing)	C++11	100 / 100	313 ms	8728 KiB

growing

#include <stdio.h>
#include <algorithm>
#define N 300002
#define NN 1048576
#define Abs(x) (x>0?x:-(x))
#define min2(x,y) (x<y?x:y)

using namespace std;
int n, nn, w[N], tree[NN];
pair<int, int> in[N];

bool cmp(pair<int, int> x, pair<int, int> y) {
	if (x.first != y.first) return x.first < y.first;
	return Abs(in[n].second - x.second) > Abs(in[n].second - y.second);
}
void Update(int lev) {
	tree[lev] = tree[lev * 2] + tree[lev * 2 + 1];
	if (lev > 1) Update(lev / 2);
}
int get_tree(int lev, int l, int r, int x, int y) {
	int mid = (l + r) / 2;
	if (r < x || y < l || x > y) return 0;
	if (x <= l && r <= y) return tree[lev];
	return get_tree(lev * 2, l, mid, x, y) + get_tree(lev * 2 + 1, mid + 1, r, x, y);
}
int main() {
	scanf("%d", &n);
	for (nn = 1; nn < n; nn *= 2);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &in[i].first);
		in[i].second = i;
	}
	sort(in + 1, in + n + 1), sort(in + 1, in + n, cmp);
	for (int i = 1; i <= n; i++) w[in[i].second] = i;

	int len = 0, len_Q = 0, minus, plus;
	long long out = 0;
	for (int i = n; i >= 1; i--) {
		if (in[i].first != in[i + 1].first) len += len_Q, len_Q = 0;

		if (i == n) minus = 0, plus = 0;
		else if (in[n].second < in[i].second) {
			plus = (in[i].second - in[n].second - 1) - get_tree(1, 1, nn, in[n].second + 1, in[i].second - 1);
			minus = get_tree(1, 1, nn, in[i].second + 1, n) * 2;
		}
		else {
			plus = (in[n].second - in[i].second - 1) - get_tree(1, 1, nn, in[i].second + 1, in[n].second - 1);
			minus = get_tree(1, 1, nn, 1, in[i].second - 1) * 2;
		}

		out += (long long)plus + (long long)min2(0, len - minus);
		len_Q++, tree[in[i].second + nn - 1] = 1;
		Update((in[i].second + nn - 1) / 2);
	} printf("%lld", out);
}

Compilation message (stderr)

growing.cpp: In function 'int main()':
growing.cpp:27:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
growing.cpp:30:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &in[i].first);
                            ^

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