oj.uz

Submission #163192

# Submission time Handle Problem Language Result Execution time Memory
163192 2019-11-11T17:59:43 Z TadijaSebez 즐거운 채소 기르기 (JOI14_growing) C++11
100 / 100
 148 ms 9316 KB 
#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

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.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 420 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 400 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 4 ms 504 KB Output is correct
9 Correct 4 ms 508 KB Output is correct
10 Correct 4 ms 504 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1780 KB Output is correct
2 Correct 57 ms 3436 KB Output is correct
3 Correct 78 ms 4328 KB Output is correct
4 Correct 112 ms 6280 KB Output is correct
5 Correct 68 ms 6524 KB Output is correct
6 Correct 41 ms 3412 KB Output is correct
7 Correct 52 ms 5764 KB Output is correct
8 Correct 137 ms 9188 KB Output is correct
9 Correct 129 ms 8548 KB Output is correct
10 Correct 148 ms 9316 KB Output is correct