oj.uz

Submission #200506

# Submission time Handle Problem Language Result Execution time Memory
200506 2020-02-07T03:03:13 Z arnold518 즐거운 채소 기르기 (JOI14_growing) C++14
0 / 100
 28 ms 6128 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 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

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

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 8 ms 4984 KB Output is correct
3 Correct 8 ms 4984 KB Output is correct
4 Correct 8 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 7 ms 4984 KB Output is correct
9 Correct 8 ms 4988 KB Output is correct
10 Incorrect 8 ms 4984 KB Output isn't correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Incorrect 8 ms 5112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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