oj.uz

답안 #25753

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25753 2017-06-24T04:41:40 Z 서규호(#1081) 즐거운 채소 기르기 (JOI14_growing) C++14
10 / 100
 26 ms 13036 KB 
#include <bits/stdc++.h>

#define lld long long
#define pp pair<int,int>
#define pb push_back
#define MOD 1000000007
#define left lleft
#define right rright
#define INF 2000000000
#define Linf 1000000000000000000LL
#define next nnext
#define minus mminus

using namespace std;

int N,nn; lld ans;
int a[300002];
lld d1[300002],d2[300002];
int seg[1200000];
vector<int> X;

void update(int x){
	x += (nn-1);
	while(x){
		seg[x]++;
		x /= 2;
	}
}
int get(int node,int l,int r,int x){
	if(r <= x) return 0;
	if(x < l) return seg[node];
	int mid = (l+r)/2;
	return get(node*2,l,mid,x)+get(node*2+1,mid+1,r,x);
}
void clear(){
	for(int i=0; i<sizeof(seg)/sizeof(int); i++) seg[i] = 0;
}

int main(){
	scanf("%d",&N);
	int big = -1,it;
	for(int i=1; i<=N; i++){
		scanf("%d",&a[i]);
		if(big < a[i]){
			big = a[i];
			it = i;
		}
		X.pb(a[i]);
	}
	sort(X.begin(),X.end());
	X.erase(unique(X.begin(),X.end()),X.end());
	for(nn=1; nn<X.size(); nn*=2);
	for(int i=1; i<=N; i++) a[i] = lower_bound(X.begin(),X.end(),a[i])-X.begin()+1;
	for(int i=1; i<N; i++){
		int t;
		if(i < it) t = i;
		else t = i+1;
		int cnt = get(1,1,nn,a[t]);
		d1[i] = d1[i-1]+cnt;
		update(a[t]);
	}
	clear();
	for(int i=1; i<N; i++){
		int t;
		if(it < N-i+1) t = N-i+1;
		else t = N-i;
		int cnt = get(1,1,nn,a[t]);
		d2[i] = d2[i-1]+cnt;
		update(a[t]);
	}
	ans = Linf;
	for(int i=1; i<=N; i++){
		ans = min(ans,d1[i-1]+d2[N-i]+abs(i-it));
	}
	printf("%lld\n",ans);

	return 0;
}

Compilation message

growing.cpp: In function 'void clear()':
growing.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<sizeof(seg)/sizeof(int); i++) seg[i] = 0;
                ^
growing.cpp: In function 'int main()':
growing.cpp:52:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(nn=1; nn<X.size(); nn*=2);
              ^
growing.cpp:40:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
                ^
growing.cpp:43:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
growing.cpp:41:15: warning: 'it' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int big = -1,it;
               ^

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 12568 KB Output is correct
2 Correct 0 ms 12568 KB Output is correct
3 Correct 0 ms 12568 KB Output is correct
4 Correct 0 ms 12568 KB Output is correct
5 Correct 0 ms 12568 KB Output is correct
6 Correct 0 ms 12568 KB Output is correct
7 Correct 0 ms 12568 KB Output is correct
8 Incorrect 0 ms 12568 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 55.0

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