Submission #200509

#	Time	Username	Problem	Language	Result	Execution time	Memory
200509		arnold518	즐거운 채소 기르기 (JOI14_growing)	C++14	100 / 100	136 ms	13020 KiB

growing

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;

int N, A[MAXN+10];
ll ans;

struct BIT
{
	ll tree[MAXN+10];
	BIT() { memset(tree, 0, sizeof(tree)); }
	void update(int i, int v) { for(; i<=N; i+=(i&-i)) tree[i]+=v; }
	ll query(int i) { ll ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
} bit;

int main()
{
	int i, j;
	scanf("%d", &N);
	for(i=1; i<=N; i++) scanf("%d", &A[i]);

	vector<pii> V;
	for(i=1; i<=N; i++) V.push_back({A[i], i});
	sort(V.begin(), V.end());

	bit=BIT();
	for(i=1; i<=N; i++) bit.update(i, 1);

	for(i=0; i<V.size();)
	{
		int p=V[i].first;
		vector<int> T;
		for(; i<V.size() && V[i].first==p; i++) T.push_back(V[i].second);
		for(auto it : T) bit.update(it, -1);
		for(auto it : T) ans+=min(bit.query(it-1), bit.query(N)-bit.query(it));
	}
	
	printf("%lld", ans);
}

Compilation message (stderr)

growing.cpp: In function 'int main()':
growing.cpp:34:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<V.size();)
           ~^~~~~~~~~
growing.cpp:38:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; i<V.size() && V[i].first==p; i++) T.push_back(V[i].second);
         ~^~~~~~~~~
growing.cpp:23:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
growing.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
growing.cpp:25:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d", &A[i]);
                      ~~~~~^~~~~~~~~~~~~

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