結果

問題 No.318 学学学学学
ユーザー asugen0402asugen0402
提出日時 2019-02-08 14:34:44
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 98 ms / 2,000 ms
コード長 8,584 bytes
コンパイル時間 783 ms
コンパイル使用メモリ 31,660 KB
実行使用メモリ 7,244 KB
最終ジャッジ日時 2023-09-04 21:19:07
合計ジャッジ時間 3,901 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
5,084 KB
testcase_01 AC 14 ms
5,560 KB
testcase_02 AC 17 ms
5,668 KB
testcase_03 AC 11 ms
5,440 KB
testcase_04 AC 14 ms
5,576 KB
testcase_05 AC 98 ms
7,244 KB
testcase_06 AC 82 ms
7,060 KB
testcase_07 AC 66 ms
6,416 KB
testcase_08 AC 55 ms
5,896 KB
testcase_09 AC 46 ms
5,592 KB
testcase_10 AC 34 ms
5,184 KB
testcase_11 AC 96 ms
7,204 KB
testcase_12 AC 64 ms
7,168 KB
testcase_13 AC 53 ms
6,412 KB
testcase_14 AC 43 ms
5,924 KB
testcase_15 AC 36 ms
5,604 KB
testcase_16 AC 29 ms
5,156 KB
testcase_17 AC 52 ms
7,164 KB
testcase_18 AC 43 ms
7,160 KB
testcase_19 AC 51 ms
7,032 KB
testcase_20 AC 25 ms
5,172 KB
testcase_21 AC 2 ms
4,836 KB
testcase_22 AC 1 ms
4,816 KB
testcase_23 AC 1 ms
4,836 KB
testcase_24 AC 1 ms
4,700 KB
testcase_25 AC 1 ms
4,824 KB
testcase_26 AC 2 ms
4,836 KB
testcase_27 AC 1 ms
4,744 KB
testcase_28 AC 2 ms
4,792 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_ARRAY_MAX		100000									// 最大配列数
#define D_SEGT_CNT		131072									// セグメントツリーデータ数(2の累乗)
#define D_SEGT_INI		0										// セグメントツリー初期値
#define D_TREE_MAX		D_ARRAY_MAX								// 木の最大データ数
#define D_TREE_WCNT		2										// 木の方向数
#define D_TREE_LEFT		0										// 木の方向 - 左側
#define D_TREE_RIGHT	1										// 木の方向 - 右側

// 内部構造体 - 木構造
typedef struct Tree {
	int miVal;													// 値
	int miMin;													// 最小位置
	int miMax;													// 最大位置
	int mi1Height[D_TREE_WCNT];									// 木の高さ
	struct Tree *mzp1Child[D_TREE_WCNT];						// 子
} Tree;

// 内部変数
static FILE *szpFpI;											// 入力
static int si1Array[D_ARRAY_MAX];								// 配列
static int siACnt;												// 配列数
static int si1SegT[D_SEGT_CNT * 2];								// セグメントツリー
static Tree sz1Tree[D_TREE_MAX];								// 木の実データ
static int siTCnt;												// 木の実データ数
static Tree *szpTop;											// 先頭の木データ

// セグメントツリー - 更新
int
fSegTUp(
	int piUpS					// <I> 更新範囲 - 開始 0～
	, int piUpE					// <I> 更新範囲 - 終了 0～
	, int piUpVal				// <I> 更新値
	, int piSNo					// <I> セグメント木の配列番号 1～
	, int piSCrgS				// <I> セグメント木の担当範囲 - 開始 0～
	, int piSCrgE				// <I> セグメント木の担当範囲 - 終了 0～
)
{
	// 範囲外チェック
	if (piUpE < piSCrgS || piSCrgE < piUpS) {
		return 0;
	}

	// 範囲内チェック
	if (piUpS <= piSCrgS && piSCrgE <= piUpE) {
		si1SegT[piSNo] = piUpVal;							// 更新
		return 0;
	}

	// 更新済みの場合、子に展開しておく
	if (si1SegT[piSNo] != D_SEGT_INI) {					// 更新済み
		si1SegT[piSNo * 2] = si1SegT[piSNo];
		si1SegT[piSNo * 2 + 1] = si1SegT[piSNo];
		si1SegT[piSNo] = D_SEGT_INI;						// 自分を初期化
	}

	// 範囲の半分
	int liHalf = (piSCrgE - piSCrgS + 1) / 2;

	// 両側の子へ
	fSegTUp(piUpS, piUpE, piUpVal, piSNo * 2, piSCrgS, piSCrgS + liHalf - 1);
	fSegTUp(piUpS, piUpE, piUpVal, piSNo * 2 + 1, piSCrgE - liHalf + 1, piSCrgE);

	return 0;
}

// セグメントツリー - 取得
int
fSegTGet(
	int piSNo					// <I> セグメント木の配列番号 1～
)
{
	int liRet;

	// 初期値
	liRet = si1SegT[piSNo];

	// 親に値があれば更新
	while (piSNo > 1) {
		piSNo /= 2;								// 上位へ
		if (si1SegT[piSNo] != D_SEGT_INI) {		// 更新済み
			liRet = si1SegT[piSNo];
		}
	}

	return liRet;
}


// 木データ - 作成
Tree *
fTreeMake(
	int piVal					// <I> 値
	, int piNo					// <I> 位置
)
{
	// 対象の木データ
	Tree *lzpTree = &(sz1Tree[siTCnt]);
	siTCnt++;

	// データセット
	memset(lzpTree, 0, sizeof(Tree));		// 初期化
	lzpTree->miVal = piVal;					// 値
	lzpTree->miMin = piNo;					// 最小位置
	lzpTree->miMax = piNo;					// 最大位置

	return lzpTree;
}

// 木データ - 比較 - 値昇順
int
fTreeCmp(
	Tree *pzpTree				// <I> 木データ
	, int piVal					// <I> 値
)
{
	// 値昇順
	if (piVal < pzpTree->miVal) {			// 左側
		return -1;
	}
	else if (piVal > pzpTree->miVal) {		// 右側
		return 1;
	}

	return 0;
}

// 木データ - 高さ取得
int
fTreeGetHeight(
	Tree *pzpTree				// <I> 対象の木情報
)
{
	// データ有無
	if (pzpTree == NULL) {
		return 0;
	}

	if (pzpTree->mi1Height[D_TREE_LEFT] >= pzpTree->mi1Height[D_TREE_RIGHT]) {
		return pzpTree->mi1Height[D_TREE_LEFT] + 1;
	}
	else {
		return pzpTree->mi1Height[D_TREE_RIGHT] + 1;
	}
}

// 木データ - 右回転(親は子の右下へ・子は親の左上へ)
int
fTreeRttR(
	Tree **pzppTree				// <I> 回転対象
)
{
	// 現在の子
	Tree *lzpChild = (*pzppTree)->mzp1Child[D_TREE_LEFT];

	// 右回転
	(*pzppTree)->mzp1Child[D_TREE_LEFT] = lzpChild->mzp1Child[D_TREE_RIGHT];	// 親の左側 = 子の右側
	(*pzppTree)->mi1Height[D_TREE_LEFT] = lzpChild->mi1Height[D_TREE_RIGHT];	// 親の高さ(左) = 子の高さ(右)
	lzpChild->mzp1Child[D_TREE_RIGHT] = *pzppTree;								// 子の右側 = 親
	lzpChild->mi1Height[D_TREE_RIGHT] = fTreeGetHeight(*pzppTree);				// 子の高さ(右) - 親の高さ
	*pzppTree = lzpChild;														// 親 = 子

	return 0;
}

// 木データ - 左回転(親は子の左下へ・子は親の右上へ)
int
fTreeRttL(
	Tree **pzppTree				// <I> 回転対象
)
{
	// 現在の子
	Tree *lzpChild = (*pzppTree)->mzp1Child[D_TREE_RIGHT];

	// 左回転
	(*pzppTree)->mzp1Child[D_TREE_RIGHT] = lzpChild->mzp1Child[D_TREE_LEFT];	// 親の右側 = 子の左側
	(*pzppTree)->mi1Height[D_TREE_RIGHT] = lzpChild->mi1Height[D_TREE_LEFT];	// 親の高さ(右) = 子の高さ(左)
	lzpChild->mzp1Child[D_TREE_LEFT] = *pzppTree;								// 子の左側 = 親
	lzpChild->mi1Height[D_TREE_LEFT] = fTreeGetHeight(*pzppTree);				// 子の高さ(左) - 親の高さ
	*pzppTree = lzpChild;														// 親 = 子

	return 0;
}

// 木データ - 追加・削除の共通処理
// 戻り値：[1]高さの変更あり [0]高さの変更なし
int
fTreeComAddDel(
	Tree **pzppNow				// <I> 現在の木情報
	, int piWay					// <I> 対象の方向
)
{
	// 高さの変更があるかチェック
	int liNew = fTreeGetHeight((*pzppNow)->mzp1Child[piWay]);
	if ((*pzppNow)->mi1Height[piWay] == liNew) {												// 変化なし
		return 0;
	}
	(*pzppNow)->mi1Height[piWay] = liNew;														// 更新

	// 高さが離れている場合、回転
	if ((*pzppNow)->mi1Height[D_TREE_LEFT] - (*pzppNow)->mi1Height[D_TREE_RIGHT] > 1) {			// 左側が高い
		fTreeRttR(pzppNow);																			// 右回転
	}
	else if ((*pzppNow)->mi1Height[D_TREE_RIGHT] - (*pzppNow)->mi1Height[D_TREE_LEFT] > 1) {	// 右側が高い
		fTreeRttL(pzppNow);																			// 左回転
	}

	return 1;
}

// 木データ - 追加
// 戻り値：[1]高さの変更あり [0]高さの変更なし [-1]追加なし
int
fTreeAdd(
	Tree **pzppNow				// <I> 現在の木情報
	, int piVal					// <I> 値
	, int piNo					// <I> 位置
)
{
	// 作成
	if (*pzppNow == NULL) {
		*pzppNow = fTreeMake(piVal, piNo);
		return 1;
	}

	// 比較
	int liRet = fTreeCmp(*pzppNow, piVal);

	// 一致
	if (liRet == 0) {
		(*pzppNow)->miMax = piNo;											// 最大位置 - 更新
		return -1;
	}

	// 方向の判別
	int liWay;
	if (liRet < 0) {													// 左側
		liWay = D_TREE_LEFT;
	}
	else {																// 右側
		liWay = D_TREE_RIGHT;
	}

	// 下位へ
	liRet = fTreeAdd(&((*pzppNow)->mzp1Child[liWay]), piVal, piNo);
	if (liRet < 1) {													// 高さの変更なし or 追加なし
		return liRet;
	}

	// 追加・削除の共通処理
	return fTreeComAddDel(pzppNow, liWay);
}

// 木データ - 全データのループ
int
fTreeAll(
	Tree *pzpNow				// <I> 現在の木情報
)
{
	// データ有無
	if (pzpNow == NULL) {
		return 0;
	}

	// 左側
	fTreeAll(pzpNow->mzp1Child[D_TREE_LEFT]);

	// セグメントツリー - 更新
	fSegTUp(pzpNow->miMin, pzpNow->miMax, pzpNow->miVal, 1, 0, D_SEGT_CNT - 1);

	// 右側
	fTreeAll(pzpNow->mzp1Child[D_TREE_RIGHT]);

	return 0;
}

// 実行メイン
int
fMain(
	int piTNo					// <I> テスト番号 1～
)
{
	int i;
	char lc1Buf[1024];

	// データ - 初期化
	memset(si1SegT, 0, sizeof(si1SegT));						// セグメントツリー
	siTCnt = 0;													// 木の実データ数
	szpTop = NULL;												// 先頭の木データ

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);
	szpFpI = fopen(lc1Buf, "r");
#else
	szpFpI = stdin;
#endif

	// 配列数 - 取得
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d", &siACnt);

	// 配列 - 取得
	for (i = 0; i < siACnt; i++) {
		int liVal;
		fscanf(szpFpI, "%d", &liVal);

		// 木 - 追加
		fTreeAdd(&szpTop, liVal, i);
	}
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);

	// 木の数でループ
	fTreeAll(szpTop);

	// セグメントツリー - 取得
	for (i = 0; i < siACnt; i++) {
		si1Array[i] = fSegTGet(D_SEGT_CNT + i);
	}

	// 結果 - １つ目
	printf("%d", si1Array[0]);

	// 結果 - ２つ目以降
	for (i = 1; i < siACnt; i++) {
		printf(" %d", si1Array[i]);
	}

	// 改行
	printf("\n");

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
#endif

	return 0;
}

int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		fMain(i);
	}
#else
	fMain(0);
#endif

	return 0;
}
0