Submission #163192

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
163192	2019-11-11 17:59:43	TadijaSebez	즐거운 채소 기르기 (JOI14_growing)	C++11	100 / 100	148 ms	9316 KiB

growing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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