oj.uz

Submission #199365

# Submission time Handle Problem Language Result Execution time Memory
199365 2020-01-31T17:24:15 Z arnold518 즐거운 채소 기르기 (JOI14_growing) C++14
30 / 100
 31 ms 6772 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5112 KB Output is correct
2 Correct 8 ms 4980 KB Output is correct
3 Correct 8 ms 4988 KB Output is correct
4 Correct 8 ms 4984 KB Output is correct
5 Correct 8 ms 4860 KB Output is correct
6 Correct 8 ms 4984 KB Output is correct
7 Correct 9 ms 4984 KB Output is correct
8 Correct 9 ms 4984 KB Output is correct
9 Correct 8 ms 4984 KB Output is correct
10 Correct 9 ms 4984 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 6772 KB Output isn't correct
2 Halted 0 ms 0 KB -