Submission #200506

#	Time	Username	Problem	Language	Result	Execution time	Memory
200506		arnold518	즐거운 채소 기르기 (JOI14_growing)	C++14	0 / 100	28 ms	6128 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(auto it : V)
	{
		int t=it.second;
		ans+=min(bit.query(t-1), bit.query(N)-bit.query(t));
		bit.update(t, -1);
	}
	
	printf("%lld", ans);
}

Compilation message (stderr)

growing.cpp: In function 'int main()':
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: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 15
• Subtask 4: 0 / 55