Submission #199365

#	Time	Username	Problem	Language	Result	Execution time	Memory
199365		arnold518	즐거운 채소 기르기 (JOI14_growing)	C++14	30 / 100	31 ms	6772 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 L[MAXN+10], R[MAXN+10];
vector<int> comp;
int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1; }

struct BIT
{
	ll tree[MAXN+10];
	BIT() { memset(tree, 0, sizeof(tree)); }
	void update(int i) { for(; i<=N; i+=(i&-i)) tree[i]++; }
	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]), comp.push_back(A[i]);

	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());
	for(i=1; i<=N; i++) A[i]=getcomp(A[i]);

	bit=BIT();
	for(i=1; i<=N; i++)
	{
		L[i]=L[i-1]+bit.query(N)-bit.query(A[i]);
		bit.update(A[i]);
	}

	bit=BIT();
	for(i=N; i>=1; i--)
	{
		R[i]=R[i+1]+bit.query(N)-bit.query(A[i]);
		bit.update(A[i]);
	}

	ll ans=1e18;
	for(i=0; i<=N; i++) ans=min(ans, L[i]+R[i+1]);
	printf("%lld", ans);
}

Compilation message (stderr)

growing.cpp: In function 'int main()':
growing.cpp:25:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
growing.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
growing.cpp:27:40: 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]), comp.push_back(A[i]);
                      ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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