oj.uz

답안 #25769

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25769 2017-06-24T05:42:32 Z 윤교준(#1083) 즐거운 채소 기르기 (JOI14_growing) C++11
100 / 100
 246 ms 13964 KB 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MAXN (300005)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
const int MX = 524288;
struct SEG {
	int d[MX*2];
	void upd(int X, int R) { for(X += MX, d[X]=R, X /= 2; X; X /= 2) d[X] = d[X*2] + d[X*2+1]; }
	int get(int s, int e) {
		int r = 0; for(s += MX, e += MX; s <= e; s /= 2, e /= 2) {
			if(s&1) r += d[s++]; if(~e&1) r += d[e--];
		} return r;
	}
};

SEG seg;
int T[MAXN][2];
int A[MAXN], P[MAXN];
ll Ans;
int N;

int main() {
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
	for(int i = 1; i <= N; i++) P[i] = i;
	sort(P+1, P+N+1, [&](const int& a, const int& b) -> bool {
		return A[a] != A[b] ? A[a] < A[b] : a < b;
	});
	for(int i = 1; i <= N; i++) seg.upd(i, 1);
	for(int i = 1, j; i <= N; i = j) {
		for(j = i+1; j <= N && A[P[i]] == A[P[j]]; j++);
		for(int k = i; k < j; k++) seg.upd(P[k], 0);
		for(int k = i; k < j; k++) {
			T[k][0] = seg.get(1, P[k]);
			T[k][1] = seg.get(P[k], N);
		}
		vector<ll> V; V.pb(0);
		for(int k = i; k < j; k++) V.back() += T[k][0];
		for(int k = j-1; i <= k; k--) V.pb(V.back() - T[k][0] + T[k][1]);
		Ans += *min_element(allv(V));
	}
	printf("%lld\n", Ans);
	return 0;
}

Compilation message

growing.cpp: In function 'int main()':
growing.cpp:54:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
growing.cpp:55:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
                                                ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 10808 KB Output is correct
2 Correct 0 ms 10808 KB Output is correct
3 Correct 0 ms 10808 KB Output is correct
4 Correct 0 ms 10808 KB Output is correct
5 Correct 0 ms 10808 KB Output is correct
6 Correct 0 ms 10808 KB Output is correct
7 Correct 0 ms 10808 KB Output is correct
8 Correct 0 ms 10808 KB Output is correct
9 Correct 0 ms 10808 KB Output is correct
10 Correct 0 ms 10808 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 10808 KB Output is correct
2 Correct 0 ms 10808 KB Output is correct
3 Correct 0 ms 10808 KB Output is correct
4 Correct 0 ms 10808 KB Output is correct
5 Correct 0 ms 10808 KB Output is correct
6 Correct 0 ms 10808 KB Output is correct
7 Correct 0 ms 10808 KB Output is correct
8 Correct 0 ms 10808 KB Output is correct
9 Correct 0 ms 10808 KB Output is correct
10 Correct 0 ms 10808 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 10808 KB Output is correct
2 Correct 0 ms 10808 KB Output is correct
3 Correct 0 ms 10808 KB Output is correct
4 Correct 3 ms 10808 KB Output is correct
5 Correct 3 ms 10808 KB Output is correct
6 Correct 0 ms 10948 KB Output is correct
7 Correct 0 ms 10948 KB Output is correct
8 Correct 3 ms 10808 KB Output is correct
9 Correct 3 ms 10808 KB Output is correct
10 Correct 3 ms 10808 KB Output is correct

Subtask #4
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 10808 KB Output is correct
2 Correct 93 ms 10808 KB Output is correct
3 Correct 106 ms 11276 KB Output is correct
4 Correct 163 ms 11276 KB Output is correct
5 Correct 126 ms 10808 KB Output is correct
6 Correct 66 ms 10808 KB Output is correct
7 Correct 173 ms 12932 KB Output is correct
8 Correct 223 ms 10808 KB Output is correct
9 Correct 239 ms 13964 KB Output is correct
10 Correct 246 ms 10808 KB Output is correct