oj.uz

Submission #25772

# Submission time Handle Problem Language Result Execution time Memory
25772 2017-06-24T05:46:11 Z 김동현(#1079) 즐거운 채소 기르기 (JOI14_growing) C++14
0 / 100
 19 ms 11396 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, a[300010], x[300010];
ll pf[300010], sf[300010], ans = 1e18;

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

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", a + i);
		x[i] = a[i];
	}
	sort(x + 1, x + n + 1);
	for(int i = 1; i <= n; i++) a[i] = (int)(lower_bound(x + 1, x + n + 1, a[i]) - x);
	for(int i = 1; i <= n; i++){
		pf[i] = pf[i - 1] + L.get(a[i], n);
		sf[n + 1 - i] = sf[n + 2 - i] + R.get(a[n + 1 - i], n);
		L.upd(a[i]);
		R.upd(a[n + 1 - i]);
	}
	for(int i = 1; i < n; i++) ans = min(ans, pf[i] + sf[i + 1]);
	printf("%lld", ans);
}

Compilation message

growing.cpp: In function 'int main()':
growing.cpp:16:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
growing.cpp:18:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
                     ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11396 KB Output is correct
2 Correct 0 ms 11396 KB Output is correct
3 Incorrect 0 ms 11396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 11396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 11396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 11396 KB Output isn't correct
2 Halted 0 ms 0 KB -