oj.uz

Submission #39507

# Submission time Handle Problem Language Result Execution time Memory
39507 2018-01-16T07:10:45 Z 14kg 즐거운 채소 기르기 (JOI14_growing) C++11
100 / 100
 313 ms 8728 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;
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

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

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

Subtask #2
20.0 / 20.0

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

Subtask #3
15.0 / 15.0

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

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8728 KB Output is correct
2 Correct 96 ms 8728 KB Output is correct
3 Correct 173 ms 8728 KB Output is correct
4 Correct 206 ms 8728 KB Output is correct
5 Correct 166 ms 8728 KB Output is correct
6 Correct 83 ms 8728 KB Output is correct
7 Correct 246 ms 8728 KB Output is correct
8 Correct 246 ms 8728 KB Output is correct
9 Correct 313 ms 8728 KB Output is correct
10 Correct 283 ms 8728 KB Output is correct