oj.uz

Submission #25797

# Submission time Handle Problem Language Result Execution time Memory
25797 2017-06-24T07:32:49 Z 서규호(#1081) 즐거운 채소 기르기 (JOI14_growing) C++14
100 / 100
 406 ms 212764 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];
int seg[1200000];
vector<int> X;
deque<int> tmp[300002];

int get(int node,int l,int r,int s,int e){
	if(r < s || e < l || s > e) return 0;
	if(s <= l && r <= e) return seg[node];
	int mid = (l+r)/2;
	return get(node*2,l,mid,s,e)+get(node*2+1,mid+1,r,s,e);
}
void update(int x){
	x += (nn-1);
	while(x){
		seg[x]--;
		x /= 2;
	}
}

int main(){
	scanf("%d",&N);
	for(int i=1; i<=N; i++){
		scanf("%d",&a[i]);
		X.pb(a[i]);
	}
	sort(X.begin(),X.end());
	X.erase(unique(X.begin(),X.end()),X.end());
	for(int i=1; i<=N; i++){
		a[i] = lower_bound(X.begin(),X.end(),a[i])-X.begin()+1;
		tmp[a[i]].pb(i);
	}
	for(nn=1; nn<N; nn*=2);
	for(int i=nn; i<nn+N; i++) seg[i] = 1;
	for(int i=nn-1; i>=1; i--) seg[i] = seg[i*2]+seg[i*2+1];
	for(int i=1; i<=X.size(); i++){
		while(tmp[i].size() != 0){
			int it1,it2;
			int lcnt,rcnt;
			it1 = tmp[i].front();
			it2 = tmp[i].back();
			lcnt = get(1,1,nn,1,it1-1);
			rcnt = get(1,1,nn,it2+1,N);
			if(lcnt <= rcnt){
				tmp[i].pop_front();
				update(it1);
			}else{
				tmp[i].pop_back();
				update(it2);
			}
			ans += min(lcnt,rcnt);
		}
	}
	printf("%lld\n",ans);

	return 0;
}

Compilation message

growing.cpp: In function 'int main()':
growing.cpp:51:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<=X.size(); i++){
                ^
growing.cpp:37:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
                ^
growing.cpp:39:20: 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 73 ms 209520 KB Output is correct
2 Correct 73 ms 209520 KB Output is correct
3 Correct 56 ms 209520 KB Output is correct
4 Correct 103 ms 209520 KB Output is correct
5 Correct 86 ms 209520 KB Output is correct
6 Correct 89 ms 209520 KB Output is correct
7 Correct 99 ms 209520 KB Output is correct
8 Correct 86 ms 209520 KB Output is correct
9 Correct 96 ms 209520 KB Output is correct
10 Correct 69 ms 209520 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 209520 KB Output is correct
2 Correct 66 ms 209520 KB Output is correct
3 Correct 76 ms 209520 KB Output is correct
4 Correct 69 ms 209520 KB Output is correct
5 Correct 76 ms 209520 KB Output is correct
6 Correct 73 ms 209520 KB Output is correct
7 Correct 106 ms 209520 KB Output is correct
8 Correct 86 ms 209520 KB Output is correct
9 Correct 83 ms 209520 KB Output is correct
10 Correct 83 ms 209520 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 209520 KB Output is correct
2 Correct 109 ms 209520 KB Output is correct
3 Correct 119 ms 209520 KB Output is correct
4 Correct 119 ms 209520 KB Output is correct
5 Correct 86 ms 209520 KB Output is correct
6 Correct 93 ms 209520 KB Output is correct
7 Correct 99 ms 209520 KB Output is correct
8 Correct 109 ms 209520 KB Output is correct
9 Correct 106 ms 209520 KB Output is correct
10 Correct 99 ms 209520 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 209916 KB Output is correct
2 Correct 203 ms 210300 KB Output is correct
3 Correct 276 ms 211068 KB Output is correct
4 Correct 333 ms 211068 KB Output is correct
5 Correct 219 ms 211068 KB Output is correct
6 Correct 156 ms 210300 KB Output is correct
7 Correct 266 ms 212764 KB Output is correct
8 Correct 406 ms 212604 KB Output is correct
9 Correct 363 ms 212604 KB Output is correct
10 Correct 386 ms 212604 KB Output is correct