Submission #3052340


Source Code Expand

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

// 内部定数
#define D_BOX_MAX		100000									// 最大箱数
#define D_SEGT_CNT		131072									// セグメントツリーデータ数(2の17乗)

// 内部構造体 - 箱情報
typedef struct Box {
	int miW;													// 幅
	int miH;													// 高さ
} Box;

// 内部変数
static Box sz1Box[D_BOX_MAX];									// 箱
static int siBCnt;												// 箱数
static int si1SegT[D_SEGT_CNT * 2];								// セグメントツリー[高さ] = 箱数

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpT, *szpFpA;
#endif

// ソート関数 - 高さ昇順
int
fSortFncH(
	const void *pzpVal1			// <I> 値1
	, const void *pzpVal2		// <I> 値2
)
{
	Box *lzpVal1 = (Box *)pzpVal1;
	Box *lzpVal2 = (Box *)pzpVal2;

	// 高さ昇順
	if (lzpVal1->miH > lzpVal2->miH) {
		return(1);
	}
	else if (lzpVal1->miH < lzpVal2->miH) {
		return(-1);
	}

	return 0;
}

// ソート関数 - 幅昇順 - 高さ降順
int
fSortFncW(
	const void *pzpVal1			// <I> 値1
	, const void *pzpVal2		// <I> 値2
)
{
	Box *lzpVal1 = (Box *)pzpVal1;
	Box *lzpVal2 = (Box *)pzpVal2;

	// 幅昇順
	if (lzpVal1->miW > lzpVal2->miW) {
		return(1);
	}
	else if (lzpVal1->miW < lzpVal2->miW) {
		return(-1);
	}

	// 高さ降順
	if (lzpVal1->miH > lzpVal2->miH) {
		return(-1);
	}
	else if (lzpVal1->miH < lzpVal2->miH) {
		return(1);
	}

	return 0;
}

// セグメントツリー - 取得
int
fSegTGet(
	int piNNo					// <I> 現在番号 1~
	, int piNowS				// <I> 現在範囲 - 開始 0~D_SEGT_CNT-1
	, int piNowE				// <I> 現在範囲 - 終了 0~D_SEGT_CNT-1
	, int piGetS				// <I> 取得範囲 - 開始 0~D_SEGT_CNT-1
	, int piGetE				// <I> 取得範囲 - 終了 0~D_SEGT_CNT-1
)
{
	// 内包チェック
	if (piGetS <= piNowS && piNowE <= piGetE) {
		return si1SegT[piNNo];
	}

	// 中間位置
	int liCenter = (piNowS + piNowE) / 2;

	int liRet = 0;

	// 左側
	if (piGetS <= liCenter) {
		liRet = fSegTGet(piNNo * 2, piNowS, liCenter, piGetS, piGetE);
	}

	// 右側
	if (piGetE >= liCenter + 1) {
		int liVal = fSegTGet(piNNo * 2 + 1, liCenter + 1, piNowE, piGetS, piGetE);
		if (liRet < liVal) {
			liRet = liVal;
		}
	}

	return liRet;
}

// セグメントツリー - 更新
int
fSegTUp(
	int piUpNo					// <I> 更新位置 0~D_SEGT_CNT-1
	, int piVal					// <I> 更新値
)
{
	// 子番号
	int liCNo1 = D_SEGT_CNT + piUpNo;
	int liCNo2;
	if (liCNo1 % 2 == 0) {
		liCNo2 = liCNo1 + 1;
	}
	else {
		liCNo2 = liCNo1 - 1;
	}

	// 更新
	si1SegT[liCNo1] = piVal;

	// 親を更新
	while (1) {

		// 親番号
		int liPNo = liCNo1 / 2;
		if (liPNo < 1) {
			break;
		}

		// 更新
		if (si1SegT[liCNo1] > si1SegT[liCNo2]) {
			si1SegT[liPNo] = si1SegT[liCNo1];
		}
		else {
			si1SegT[liPNo] = si1SegT[liCNo2];
		}

		// 次の子番号
		liCNo1 = liPNo;
		if (liCNo1 % 2 == 0) {
			liCNo2 = liCNo1 + 1;
		}
		else {
			liCNo2 = liCNo1 - 1;
		}
	}

	return 0;
}

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

	// データ初期化
	memset(si1SegT, 0, sizeof(si1SegT));						// セグメントツリー

	// テストファイルオープン
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);
	szpFpT = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#endif

	// 箱数取得
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
	fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif
	sscanf(lc1Buf, "%d", &siBCnt);

	// 箱取得
	for (i = 0; i < siBCnt; i++) {
#ifdef D_TEST
		fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
		fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif
		sscanf(lc1Buf, "%d%d", &sz1Box[i].miW, &sz1Box[i].miH);
	}

	// ソート - 高さ昇順
	qsort(sz1Box, siBCnt, sizeof(Box), fSortFncH);

	// 高さを0~siBCnt-1に更新
	for (i = 0; i < siBCnt; i++) {
		sz1Box[i].miH = i;
	}

	// ソート - 幅昇順
	qsort(sz1Box, siBCnt, sizeof(Box), fSortFncW);

	// 最大値取得
	int liMax = 0;
	for (i = 0; i < siBCnt; i++) {

		// セグメントツリー - 取得(高さ以下)
		int liCnt = fSegTGet(1, 0, D_SEGT_CNT - 1, 0, sz1Box[i].miH) + 1;
		if (liMax < liCnt) {
			liMax = liCnt;
		}

		// セグメントツリー - 更新
		fSegTUp(sz1Box[i].miH, liCnt);
	}

	// 結果セット
	sprintf(lc1Out, "%d\n", liMax);

	// 結果表示
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, lc1Out)) {
		siRes = -1;
	}
#else
	printf("%s", lc1Out);
#endif

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

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", piTNo);
	}
	else {
		printf("NG %d\n", piTNo);
	}
#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;
}

Submission Info

Submission Time
Task D - プレゼント
User asugen0402
Language C (GCC 5.4.1)
Score 30
Code Size 5254 Byte
Status WA
Exec Time 73 ms
Memory 2812 KB

Compile Error

./Main.c: In function ‘fMain’:
./Main.c:190:2: warning: ignoring return value of ‘fgets’, declared with attribute warn_unused_result [-Wunused-result]
  fgets(lc1Buf, sizeof(lc1Buf), stdin);
  ^
./Main.c:199:3: warning: ignoring return value of ‘fgets’, declared with attribute warn_unused_result [-Wunused-result]
   fgets(lc1Buf, sizeof(lc1Buf), stdin);
   ^

Judge Result

Set Name Sample Subtask0 All
Score / Max Score 0 / 0 30 / 30 0 / 70
Status
AC × 4
AC × 19
AC × 27
WA × 7
Set Name Test Cases
Sample sample0.txt, sample1.txt, sample2.txt, sample3.txt
Subtask0 subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, sample0.txt, sample1.txt, sample2.txt, sample3.txt
All sample0.txt, sample1.txt, sample2.txt, sample3.txt, subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
sample0.txt AC 1 ms 1152 KB
sample1.txt AC 1 ms 1152 KB
sample2.txt AC 1 ms 1152 KB
sample3.txt AC 1 ms 1152 KB
subtask0_0.txt AC 1 ms 1152 KB
subtask0_1.txt AC 1 ms 1152 KB
subtask0_10.txt AC 2 ms 1152 KB
subtask0_11.txt AC 2 ms 1152 KB
subtask0_12.txt AC 2 ms 1152 KB
subtask0_13.txt AC 2 ms 1152 KB
subtask0_14.txt AC 2 ms 1152 KB
subtask0_2.txt AC 1 ms 1152 KB
subtask0_3.txt AC 1 ms 1152 KB
subtask0_4.txt AC 2 ms 1152 KB
subtask0_5.txt AC 1 ms 1152 KB
subtask0_6.txt AC 2 ms 1152 KB
subtask0_7.txt AC 2 ms 1152 KB
subtask0_8.txt AC 2 ms 1152 KB
subtask0_9.txt AC 1 ms 1152 KB
subtask1_0.txt AC 44 ms 2204 KB
subtask1_1.txt AC 2 ms 1276 KB
subtask1_10.txt AC 46 ms 2428 KB
subtask1_11.txt AC 53 ms 2804 KB
subtask1_12.txt WA 73 ms 2812 KB
subtask1_13.txt WA 73 ms 2812 KB
subtask1_14.txt WA 73 ms 2812 KB
subtask1_2.txt WA 12 ms 1404 KB
subtask1_3.txt AC 62 ms 2556 KB
subtask1_4.txt WA 72 ms 2804 KB
subtask1_5.txt AC 11 ms 1404 KB
subtask1_6.txt WA 54 ms 2360 KB
subtask1_7.txt AC 29 ms 1856 KB
subtask1_8.txt AC 62 ms 2556 KB
subtask1_9.txt WA 32 ms 1916 KB