글 읽기 - 시간 초과가 왜 날까요?

hannibal3 4년 전 0

세그먼트 트리로 구현했고요..

DVD를 하나 빼서 위로 올리면 배열을 전체 업데이트가 필요하므로,,

세그먼트트리를 처음부터 n + m으로 잡았는데요... 이거 때문일까요? ㅠ

#include<stdio.h>
#include<malloc.h>

int t, n, m, base, firstplace, row, col;
int movie[100000];
int ans[101][100001];
int tm[101];

typedef struct NodeType{
	int no, isthere;
}Node;
Node node[500000];

void InitMovie(void);
void SelectMovie(void);
int GetSum(int a);
void UpdateTree(int a, int b);
void ResetNode(void);

int main(void){
	int i,j, l, tt, tmcnt=1;
	scanf("%d", &t);
	tt = t;
	while (t){
		scanf("%d %d", &n, &m);
		tm[tmcnt] = m;
		tmcnt++;
		for (i = 0; i < m; i++)scanf("%d", &movie[i]);
		InitMovie();
		col = 1;
		SelectMovie();
		ResetNode();
		t--;		
	}

	
	for (i = 1; i <= tt; i++){
		for (j = 1; j <= tm[i]; j++){
			printf("%d ", ans[i][j]);
		}
		printf("\n");
	}
	return 0;
}
void SelectMovie(void){
	int i, j,k, cnt = 1;
	row++;
	for (i = 0; i < m; i++){
		for (j = base; j < firstplace+n; j++){
			if (node[j].no == movie[i]){								
				ans[row][col] = GetSum(j - 1);
				col++;
				node[j].isthere = 0;				
				node[firstplace - cnt].no = node[j].no;
				node[j].no = 0;
				node[firstplace - cnt].isthere = 1;
				cnt++;		
				UpdateTree(j, 0);
				UpdateTree(firstplace - cnt, 1);

				/*
				printf("\n UpdateMovie : %d\n", i);
				for (k = 0; k < 16; k++) printf("%d ", node[k].isthere);
				printf("\n");
				for (k = 0; k < 16; k++) printf("%d ", node[k].no);
				*/

				break;
			}
		}
	}
}
void InitMovie(void){
	int i;
	for (base = 1; base < n + m; base=base*2);
	firstplace = base + m;
	for (i = firstplace; i < firstplace+n; i++){
		node[i].isthere = 1;
		node[i].no = i - firstplace + 1;
	}
	for (i = base - 1; i>0; i--){
		node[i].isthere = node[i * 2].isthere + node[i * 2 + 1].isthere;
	}
	/*
	printf("\n InitMovie\n");
	for (i = 0; i < 16; i++) printf("%d ", node[i].isthere);
	printf("\n");
	for (i = 0; i < 16; i++) printf("%d ", node[i].no);
	*/
}
int GetSum(int a){
	int L, R, sum=0;
	L = base, R = a;
	if (a < base)return 0;
	while (L < R){
		if (L % 2 == 1)sum = sum + node[L].isthere, L++;
		if (R % 2 == 0)sum = sum + node[R].isthere, R--;
		L = L / 2, R = R / 2;
	}
	if (L == R)sum = sum + node[L].isthere;
	return sum;
}
void UpdateTree(int a, int b){
	//node[a].isthere = b;
	a = a / 2;
	while (a){
		node[a].isthere = node[a * 2].isthere + node[a * 2 + 1].isthere;
		a = a / 2;
	}
}
void ResetNode(void){
	int i;
	for (i = 0; i <= firstplace+n; i++){
		node[i].no = 0;
		node[i].isthere = 0;
	}
}

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

문제

문제

출처

ICPC

시간 초과가 왜 날까요?

hannibal3 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말