oj.uz

Submission #25750

# Submission time Handle Problem Language Result Execution time Memory
25750 2017-06-24T04:28:00 Z 김동현(#1079) 즐거운 채소 기르기 (JOI14_growing) C++14
30 / 100
 33 ms 19588 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll 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(ll x){ for(x += sz; x; x /= 2) dat[x]++; }
	ll get(ll s, ll 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("%lld", &n);
	for(int i = 1; i <= n; i++){
		scanf("%lld", a + i);
		xx[i] = a[i];
	}
	sort(xx + 1, xx + n + 1);
	for(int i = 1; i <= n; i++){
		a[i] = (ll)(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 = n * n;
	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:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
                   ^
growing.cpp:26:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", a + i);
                       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19588 KB Output is correct
2 Correct 0 ms 19588 KB Output is correct
3 Correct 3 ms 19588 KB Output is correct
4 Correct 0 ms 19588 KB Output is correct
5 Correct 0 ms 19588 KB Output is correct
6 Correct 3 ms 19588 KB Output is correct
7 Correct 0 ms 19588 KB Output is correct
8 Correct 0 ms 19588 KB Output is correct
9 Correct 0 ms 19588 KB Output is correct
10 Correct 0 ms 19588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19588 KB Output is correct
2 Correct 0 ms 19588 KB Output is correct
3 Correct 3 ms 19588 KB Output is correct
4 Correct 0 ms 19588 KB Output is correct
5 Correct 0 ms 19588 KB Output is correct
6 Correct 0 ms 19588 KB Output is correct
7 Correct 3 ms 19588 KB Output is correct
8 Correct 3 ms 19588 KB Output is correct
9 Correct 0 ms 19588 KB Output is correct
10 Correct 3 ms 19588 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 55.0

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