글 읽기 - 어디가 틀렸는지 조언부탁드립니다.

daniel00 6년 전 0

메모리 때문에 애를먹다가, 간신히 벗어났는데 이제는 답이 틀리다고 나오네요.

어디서 실수가 있었는지 조언 부탁드립니다.

코드는 펜윅트리를 이용해서 counting inversion 하는 방식입니다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>

using namespace std;

typedef long long ll;
const int INF = 1e9 + 100;
const int MAXN = 500000;

int srcVal[MAXN + 1];	
vector<int> BIT;
int N;

void updateBIT(int idx, int val)
{
	while (idx <= N)
	{
		BIT[idx] += val;
		idx += (idx&-idx);
	}
}

ll getAccSum(int idx)
{
	ll ans = 0;
	while (idx >= 1)
	{
		ans += BIT[idx];
		idx -= (idx&-idx);
	}
	return ans;
}

void CovertValToIndex()
{
	int* srcCpy = new int[N + 1];

	for (int i = 1; i <= N; i++)
		srcCpy[i] = srcVal[i];

	sort(srcCpy + 1, srcCpy + N + 1);

	for (int i = 1; i <= N; i++)
	{
		srcVal[i] = lower_bound(srcCpy + 1, srcCpy + 1 + N, srcVal[i]) - srcCpy;
	}

	delete[] srcCpy;
}

ll getInvCnt()
{
	ll ans = 0;
	for (int i = N; i >= 1; i--)
	{
		ans += getAccSum(srcVal[i] - 1);
		updateBIT(srcVal[i], 1);
	}
	return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("sample_input.txt", "r", stdin);
#endif

	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &srcVal[i]);
	}

	CovertValToIndex();
	BIT.resize(N + 1);

	printf("%d", getInvCnt());

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 틀렸는지 조언부탁드립니다.

daniel00 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말