oj.uz

Submission #39506

# Submission time Handle Problem Language Result Execution time Memory
39506 2018-01-16T07:09:09 Z 14kg 즐거운 채소 기르기 (JOI14_growing) C++11
100 / 100
 299 ms 16340 KB 
#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

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

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

Subtask #2
20.0 / 20.0

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

Subtask #3
15.0 / 15.0

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

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16340 KB Output is correct
2 Correct 106 ms 16340 KB Output is correct
3 Correct 169 ms 16340 KB Output is correct
4 Correct 229 ms 16340 KB Output is correct
5 Correct 166 ms 16340 KB Output is correct
6 Correct 93 ms 16340 KB Output is correct
7 Correct 243 ms 16340 KB Output is correct
8 Correct 249 ms 16340 KB Output is correct
9 Correct 293 ms 16340 KB Output is correct
10 Correct 299 ms 16340 KB Output is correct