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
2018-08-21 15:40:17+0900
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
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