oj.uz

답안 #25743

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25743 2017-06-24T03:57:08 Z 김동현(#1079) 즐거운 채소 기르기 (JOI14_growing) C++14
30 / 100
 29 ms 11396 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, a[300010], xx[300010];
ll p[300010], s[300010], ans;

struct BIT{
	ll dat[300010];
	void ini(){ fill(dat + 1, dat + n + 1, 0); }
	void upd(int x){ for(; x <= n; x += x & -x) dat[x]++; }
	ll get(int x){
		ll ret = 0;
		for(; x; x -= x & -x) ret += dat[x];
		return ret;
	}
	ll get(int s, int e){ return get(e) - get(s - 1); }
} B;

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", a + i);
		xx[i] = a[i];
	}
	sort(xx + 1, xx + n + 1);
	for(int i = 1; i <= n; i++){
		a[i] = (int)(lower_bound(xx + 1, xx + n + 1, a[i]) - xx);
		p[i] = p[i - 1] + B.get(a[i] + 1, n);
		B.upd(a[i]);
	}
	B.ini();
	ans = 1e18;
	for(int i = n; i >= 1; i--){
		s[i] = s[i + 1] + B.get(a[i] + 1, n);
		B.upd(a[i]);
		if(i - 1) ans = min(ans, p[i - 1] + s[i]);
	}
	printf("%lld\n", ans);
}

Compilation message

growing.cpp: In function 'int main()':
growing.cpp:21:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
growing.cpp:23:21: 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 11396 KB Output is correct
2 Correct 0 ms 11396 KB Output is correct
3 Correct 0 ms 11396 KB Output is correct
4 Correct 0 ms 11396 KB Output is correct
5 Correct 0 ms 11396 KB Output is correct
6 Correct 0 ms 11396 KB Output is correct
7 Correct 0 ms 11396 KB Output is correct
8 Correct 0 ms 11396 KB Output is correct
9 Correct 0 ms 11396 KB Output is correct
10 Correct 0 ms 11396 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 11396 KB Output is correct
2 Correct 0 ms 11396 KB Output is correct
3 Correct 0 ms 11396 KB Output is correct
4 Correct 0 ms 11396 KB Output is correct
5 Correct 0 ms 11396 KB Output is correct
6 Correct 0 ms 11396 KB Output is correct
7 Correct 0 ms 11396 KB Output is correct
8 Correct 0 ms 11396 KB Output is correct
9 Correct 0 ms 11396 KB Output is correct
10 Correct 0 ms 11396 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 11396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 11396 KB Output isn't correct
2 Halted 0 ms 0 KB -