oj.uz

Submission #200509

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

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

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 7 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 8 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 #3
15.0 / 15.0

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

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5872 KB Output is correct
2 Correct 53 ms 7272 KB Output is correct
3 Correct 75 ms 8224 KB Output is correct
4 Correct 91 ms 9572 KB Output is correct
5 Correct 71 ms 9448 KB Output is correct
6 Correct 44 ms 7272 KB Output is correct
7 Correct 97 ms 10076 KB Output is correct
8 Correct 134 ms 11612 KB Output is correct
9 Correct 136 ms 13020 KB Output is correct
10 Correct 133 ms 11612 KB Output is correct