Submission #39506

#	Time	Username	Problem	Language	Result	Execution time	Memory
39506		14kg	즐거운 채소 기르기 (JOI14_growing)	C++11	100 / 100	299 ms	16340 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;
long long n, nn, w[N], tree[NN];
pair<long long, long long> in[N];

bool cmp(pair<long long, long long> x, pair<long long, long long> 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(long long lev) {
	tree[lev] = tree[lev * 2] + tree[lev * 2 + 1];
	if (lev > 1) Update(lev / 2);
}
long long get_tree(long long lev, long long l, long long r, long long x, long long y) {
	long long 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("%lld", &n);
	for (nn = 1; nn < n; nn *= 2);
	for (long long i = 1; i <= n; i++) {
		scanf("%lld", &in[i].first);
		in[i].second = i;
	}
	sort(in + 1, in + n + 1), sort(in + 1, in + n, cmp);
	for (long long i = 1; i <= n; i++) w[in[i].second] = i;

	long long len = 0, len_Q = 0, minus, plus, out = 0;
	for (long long 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;
		}

		//prlong longf("%lld %lld: %lld %lld\n", in[i].first, in[i].second, plus , len);
		out += plus + 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:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
                   ^
growing.cpp:30:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &in[i].first);
                              ^

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