글 읽기 - 반례 좀 찾아주세요(인덱스트리 활용)

irishw 6년 전 0

dp 가 아니라 인덱스 트리 활용해서 구현했는데,

질문들 싸~악 검색해서 기존 질문들에 반례도 다 정답으로 나오네요.

고수님들 틀린 부분 조언 부탁 드립니다.

#include <stdio.h>

#define DINF -234234234
#define MAX 1024
typedef struct TREE_
{
	int L;
	int R;
	int cntmax;
}TREE;
int data[1024];
TREE tree[2049];
int N;
void PUSH(int idx, int cnt);
int query(int idx, int start, int end);
int main(void)
{
	int ret = 1;
	int ans = 1;
	//freopen("11053_가장긴.txt", "r",stdin);
	for(int i=0; i<1024; i++)
	{
		tree[MAX+i].L = i;
		tree[MAX+i].R = i;
	}

	for(int i=MAX+1; i>=1; i--)
	{
		tree[i].L = tree[i*2].L;
		tree[i].R = tree[i*2+1].R;
	}

	scanf("%d", &N);

	scanf("%d", &data[1]);

	PUSH(data[1],1);
	for(int n=1; n< N; n++)
	{
		scanf("%d", &data[n]);
		ret = query(1, 0, data[n]-1);

		PUSH(data[n], ret+1);
		if(ans < ret+1)	ans = ret+1;
	}
	printf("%d", ans);
	return 0;
}

void PUSH(int idx, int cnt)
{
	
	int current = MAX+idx ;
	int parent = current/ 2;
	tree[MAX+idx].cntmax = cnt;

	while(current >= 1)
	{
		if (tree[parent].cntmax < tree[current].cntmax)
		{
			tree[parent].cntmax = tree[current].cntmax;
		}
		current = parent;
		parent = current/2;
	}
}

int query(int idx, int start, int end)
{
	int ret;
	int child1, child2;
	if(tree[idx].R < start || tree[idx].L > end)	return DINF;
	if(start <= tree[idx].L && tree[idx].R <= end)	return tree[idx].cntmax;

	
	child1 = query(idx*2, start,end);
	child2 = query(idx*2 +1, start,end);

	ret = child1 > child2 ? child1 : child2;
	return ret;
}

djm03178 6년 전 0

1 1

이 2로 나오네요.

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

문제

문제

출처

ICPC

반례 좀 찾아주세요(인덱스트리 활용)

irishw 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말