Submission #163192

#	Time	Username	Problem	Language	Result	Execution time	Memory
163192		TadijaSebez	즐거운 채소 기르기 (JOI14_growing)	C++11	100 / 100	148 ms	9316 KiB

growing

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=300050;
int a[N],l[N],r[N];
int main()
{
	int n;
	scanf("%i",&n);
	vector<int> all;
	for(int i=1;i<=n;i++) scanf("%i",&a[i]),all.pb(a[i]);
	sort(all.begin(),all.end());
	all.resize(unique(all.begin(),all.end())-all.begin());
	vector<int> sum(all.size()+1,0);
	auto Set=[&](int i, int f){ for(;i<=all.size();i+=i&-i) sum[i]+=f;};
	auto Get=[&](int i){ int ans=0;for(;i;i-=i&-i) ans+=sum[i];return ans;};
	for(int i=1;i<=n;i++) a[i]=lower_bound(all.begin(),all.end(),a[i])-all.begin()+1;
	for(int i=1;i<=n;i++) l[i]=Get(all.size())-Get(a[i]),Set(a[i],1);
	sum.clear();sum.resize(all.size()+1);
	for(int i=n;i>=1;i--) r[i]=Get(all.size())-Get(a[i]),Set(a[i],1);
	long long ans=0;
	for(int i=1;i<=n;i++) ans+=min(l[i],r[i]);
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

growing.cpp: In lambda function:
growing.cpp:15:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  auto Set=[&](int i, int f){ for(;i<=all.size();i+=i&-i) sum[i]+=f;};
                                   ~^~~~~~~~~~~~
growing.cpp: In function 'int main()':
growing.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
growing.cpp:11:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i",&a[i]),all.pb(a[i]);
                        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 55 / 55