oj.uz

Submission #25774

# Submission time Handle Problem Language Result Execution time Memory
25774 2017-06-24T05:52:17 Z 김동현(#1079) 즐거운 채소 기르기 (JOI14_growing) C++14
30 / 100
 1000 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 = (1LL << 60);

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];
		for(int j = 1; j < i; j++) if(a[j] > a[i]) pf[i]++;
		sf[n + 1 - i] = sf[n + 2 - i];
		for(int j = n + 2 - i; j <= n; j++) if(a[j] > a[n + 1 - i]) sf[n + 1 - i]++;
		/*
		pf[i] = pf[i - 1] + L.get(a[i] + 1, n);
		sf[n + 1 - i] = sf[n + 2 - i] + R.get(a[n + 1 - i] + 1, 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
10.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 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

# 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 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

# 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 Execution timed out 1000 ms 11396 KB Execution timed out
2 Halted 0 ms 0 KB -