oj.uz

Submission #123672

# Submission time Handle Problem Language Result Execution time Memory
123672 2019-07-02T03:31:36 Z onjo0127 즐거운 채소 기르기 (JOI14_growing) C++11
100 / 100
 141 ms 9228 KB 
#include <bits/stdc++.h>
using namespace std;

const int MXN = 300009;
int N, A[MXN], F[MXN], L[MXN], R[MXN];

void upd(int x, int y) { for(int i=x; i<=300000; i+=(i&-i)) F[i] += y; }
int get(int x) { int ret = 0; for(int i=x; i>=1; i-=(i&-i)) ret += F[i]; return ret; }

int main() {
	vector<int> X;
	scanf("%d",&N);
	for(int i=1; i<=N; i++) {
		scanf("%d",&A[i]);
		X.push_back(A[i]);
	}
	sort(X.begin(), X.end());
	for(int i=1; i<=N; i++) A[i] = lower_bound(X.begin(), X.end(), A[i]) - X.begin() + 1;
	for(int i=1; i<=N; i++) {
		L[i] = i-1 - get(A[i]);
		upd(A[i], 1);
	}
	for(int i=1; i<=300000; i++) F[i] = 0;
	for(int i=N; i>=1; i--) {
		R[i] = N-i - get(A[i]);
		upd(A[i], 1);
	}
	long long ans = 0;
	for(int i=1; i<=N; i++) ans += min(L[i], R[i]);
	printf("%lld", ans);
	return 0;
}

Compilation message

growing.cpp: In function 'int main()':
growing.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
growing.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&A[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1532 KB Output is correct
2 Correct 3 ms 1500 KB Output is correct
3 Correct 4 ms 1528 KB Output is correct
4 Correct 4 ms 1656 KB Output is correct
5 Correct 5 ms 1656 KB Output is correct
6 Correct 4 ms 1656 KB Output is correct
7 Correct 4 ms 1656 KB Output is correct
8 Correct 5 ms 1656 KB Output is correct
9 Correct 5 ms 1656 KB Output is correct
10 Correct 5 ms 1656 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2932 KB Output is correct
2 Correct 57 ms 4184 KB Output is correct
3 Correct 77 ms 5100 KB Output is correct
4 Correct 112 ms 6764 KB Output is correct
5 Correct 66 ms 6892 KB Output is correct
6 Correct 41 ms 4208 KB Output is correct
7 Correct 85 ms 6948 KB Output is correct
8 Correct 130 ms 9188 KB Output is correct
9 Correct 138 ms 9228 KB Output is correct
10 Correct 141 ms 9192 KB Output is correct