Submission #123672

#	Time	Username	Problem	Language	Result	Execution time	Memory
123672		onjo0127	즐거운 채소 기르기 (JOI14_growing)	C++11	100 / 100	141 ms	9228 KiB

growing

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 55 / 55