結果

問題 No.59 鉄道の旅
コンテスト
ユーザー asugen0402
提出日時 2019-01-25 14:07:49
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 40 ms / 5,000 ms
コード長 3,789 bytes
コンパイル時間 156 ms
コンパイル使用メモリ 32,256 KB
実行使用メモリ 10,076 KB
最終ジャッジ日時 2024-09-16 04:46:33
合計ジャッジ時間 1,343 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// 内部定数
#define D_SEGT_CNT		1048576									// セグメントツリーデータ数(2の20乗)

// 内部変数
static FILE *szpFpI;											// 入力
static int si1SegT[D_SEGT_CNT * 2];								// セグメントツリー

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

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

	// 親を更新
	while (1) {

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

		// 更新
		si1SegT[liPNo] = si1SegT[liCNo1] + si1SegT[liCNo2];

		// 次の子番号
		liCNo1 = liPNo;
		if (liCNo1 % 2 == 0) {
			liCNo2 = liCNo1 + 1;
		}
		else {
			liCNo2 = liCNo1 - 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) {
		liRet += fSegTGet(piNNo * 2 + 1, liCenter + 1, piNowE, piGetS, piGetE);
	}

	return liRet;
}

// 実行メイン
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);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 駅数・最大数 - 取得
	int liSCnt, liMCnt;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d", &liSCnt, &liMCnt);

	// 荷物 - 取得
	for (i = 0; i < liSCnt; i++) {
		int liWeight;
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d", &liWeight);

		if (liWeight > 0) {
			int liSum = fSegTGet(1, 0, D_SEGT_CNT - 1, liWeight, D_SEGT_CNT - 1);		// 合計
			if (liSum < liMCnt) {
				si1SegT[D_SEGT_CNT + liWeight]++;											// 積む
				fSegTUp(liWeight);															// 更新
			}
		}
		else {
			liWeight *= -1;
			if (si1SegT[D_SEGT_CNT + liWeight] > 0) {
				si1SegT[D_SEGT_CNT + liWeight]--;											// 降ろす
				fSegTUp(liWeight);															// 更新
			}
		}
	}

	// 現在合計
	int liSum = fSegTGet(1, 0, D_SEGT_CNT - 1, 0, D_SEGT_CNT - 1);

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

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

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	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;
}
0