글 읽기 - 도움 요청합니다

skekq123 5년 전 0

계속 예외를 찾아봐도 어느부분이 틀린지 모르겠네요... ㅠㅠ

#include<iostream>
#include<vector>
#define max_n 100000
using namespace std;

int ary[max_n + 1];
int tree[(1 << 21) + 1];
int first;
vector<int> ans;

int find(int num);
void update(int num, int i, int start);
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int T;

	cin >> T;
	
	for (int test_case = 1; test_case <= T; ++test_case)
	{
		int a, b;
		cin >> a >> b;

		int sum = a + b;
		int level = 1;
		int temp = 1;
		
		while (1)
		{
			if (temp > sum) break;
			temp <<= 1;
			++level;
		}
		
		int idx = 1;
		idx <<= (level - 1);
		first = idx;

		int start = idx + idx / 2;
		
		int end = start + a - 1;
		
		for (int i = 1; i <= a; ++i) ary[i] = start + i - 1;

		for (int i = 1; i <= end; ++i) tree[i] = 0; // 초기 셋팅

		for (int i = start; i <= end; ++i) tree[i] = 1; 

		for (int i = idx-1; i > 0; --i) tree[i] = tree[i * 2] + tree[i * 2 + 1];
		
		for (int i = 1; i <= b; ++i)
		{
			int num;
			cin >> num;
			//cout << find(ary[num]) << '\n';
			ans.push_back(find(ary[num]));
			update(num, i, start);
		}
		int ans_size;
		ans_size = ans.size();
		for (int i = 0; i < ans_size; ++i)
			cout << ans[i] << ' ';
		cout << '\n';
		ans.clear();
		
	}
	return 0;
}
void update(int num, int i, int start)
{
	int l = start - i;
	int r = ary[num];

	ary[num] = l;

	while (1)
	{
		if (l == 0) break;
		++tree[l];
		l /= 2;
	}
	while (1)
	{
		if (r == 0) break;
		--tree[r];
		r /= 2;
	}
}
int find(int num)
{
	int ans = 0;

	int l, r;
	l = first;
	r = num;

	while (1)
	{
		if (l > r) break;
		if (l % 2 == 1) ans += tree[l];
		if (r % 2 == 0) ans += tree[r];

		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
	
	return ans-1;
}

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

문제

문제

출처

ICPC

도움 요청합니다

skekq123 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말