oj.uz

답안 #25748

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

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

const int sz = 524288;
struct Seg{
	ll dat[2 * sz];
	void ini(){ fill(dat + 1, dat + 2 * sz, 0); }
	void upd(int x){ for(x += sz; x; x /= 2) dat[x]++; }
	ll get(int s, int e){
		ll ret = 0;
		for(s += sz, e += sz; s <= e; s /= 2, e /= 2){
			if(s % 2 == 1) ret += dat[s++];
			if(e % 2 == 0) ret += dat[e--];
		}
		return ret;
	}
} S;

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] + S.get(a[i] + 1, n);
		S.upd(a[i]);
	}
	S.ini();
	ans = 1e18;
	for(int i = n; i >= 1; i--){
		s[i] = s[i + 1] + S.get(a[i] + 1, n);
		S.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:24:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
growing.cpp:26: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 17244 KB Output is correct
2 Correct 3 ms 17244 KB Output is correct
3 Correct 0 ms 17244 KB Output is correct
4 Correct 3 ms 17244 KB Output is correct
5 Correct 0 ms 17244 KB Output is correct
6 Correct 0 ms 17244 KB Output is correct
7 Correct 0 ms 17244 KB Output is correct
8 Correct 0 ms 17244 KB Output is correct
9 Correct 3 ms 17244 KB Output is correct
10 Correct 3 ms 17244 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 55.0

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