結果

問題 No.743 Segments on a Polygon
ユーザー asugen0402
提出日時 2019-05-16 11:01:22
言語 C
(gcc 8.2.0)
結果
AC  
実行時間 99 ms
コード長 5,607 Byte
コンパイル時間 117 ms
使用メモリ 6,872 KB
最終ジャッジ日時 2019-08-12 17:47:53

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1.txt AC 96 ms
6,872 KB
2.txt AC 96 ms
6,872 KB
3.txt AC 96 ms
6,872 KB
4.txt AC 96 ms
6,872 KB
5.txt AC 96 ms
6,872 KB
6.txt AC 97 ms
6,872 KB
7.txt AC 99 ms
6,868 KB
8.txt AC 96 ms
6,872 KB
9.txt AC 96 ms
6,872 KB
challenge_01.txt AC 71 ms
6,872 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_LINE_MAX		100000									// 最大線数
#define D_SEGT_CNT		262144									// セグメントツリーデータ数(2の累乗)

// 内部構造体 - 線情報
typedef struct Line {
	int miSNo, miENo;											// 頂点 0~
} Line;

// 内部変数
static FILE *szpFpI;											// 入力
static Line sz1Line[D_LINE_MAX];								// 線
static int siLCnt;												// 線数
static int siVCnt;												// 頂点数
static int si1SegT[D_SEGT_CNT * 2];								// セグメントツリー
static int siSCNo;												// セグメントツリー - 子の開始位置

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

// 出力
int
fOut(
	char *pcpLine				// <I> 1行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// 数値(int) - 入れ替え
int
fSwap(
	int *pipVal1				// <IO> 値1
	, int *pipVal2				// <IO> 値2
)
{
	int liWork = *pipVal1;
	*pipVal1 = *pipVal2;
	*pipVal2 = liWork;

	return 0;
}

// ソート関数 - 頂点昇順
int
fSortFnc(
	const void *pzpVal1			// <I> 値1
	, const void *pzpVal2		// <I> 値2
)
{
	Line *lzpVal1 = (Line *)pzpVal1;
	Line *lzpVal2 = (Line *)pzpVal2;

	// 頂点昇順
	if (lzpVal1->miSNo > lzpVal2->miSNo) {
		return 1;
	}
	else if (lzpVal1->miSNo < lzpVal2->miSNo) {
		return -1;
	}

	return 0;
}

// セグメントツリー - 子の開始位置 - セット
int
fSegTSetCSNo(
	int piCnt					// <I> 子データ数
)
{
	siSCNo = 1;
	while (siSCNo < piCnt) {
		siSCNo *= 2;
	}

	return 0;
}

// セグメントツリー - 子に展開
int
fSegTExt(
	int piNo					// <I> 位置 0~
)
{
	si1SegT[piNo * 2] += si1SegT[piNo];
	si1SegT[piNo * 2 + 1] += si1SegT[piNo];
	si1SegT[piNo] = 0;

	return 0;
}

// セグメントツリー - 更新
int
fSegTUpRngMain(
	int piUpS					// <I> 更新範囲 - 開始 0~
	, int piUpE					// <I> 更新範囲 - 終了 0~
	, int piAddVal				// <I> 加算値
	, int piNNo					// <I> 現在位置 1~
	, int piNowS				// <I> 現在範囲 - 開始 0~
	, int piNowE				// <I> 現在範囲 - 終了 0~
)
{
	// 範囲外チェック
	if (piUpE < piNowS || piNowE < piUpS) {
		return 0;
	}

	// 範囲内チェック
	if (piUpS <= piNowS && piNowE <= piUpE) {
		si1SegT[piNNo] += piAddVal;							// 加算
		return 0;
	}

	// 子に展開
	fSegTExt(piNNo);

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

	// 両側の子へ
	fSegTUpRngMain(piUpS, piUpE, piAddVal, piNNo * 2, piNowS, piNowS + liHalf - 1);
	fSegTUpRngMain(piUpS, piUpE, piAddVal, piNNo * 2 + 1, piNowE - liHalf + 1, piNowE);

	return 0;
}
int
fSegTUpRng(
	int piUpS					// <I> 更新範囲 - 開始 0~
	, int piUpE					// <I> 更新範囲 - 終了 0~
	, int piAddVal				// <I> 加算値
)
{
	return fSegTUpRngMain(piUpS, piUpE, piAddVal, 1, 0, siSCNo - 1);
}

// セグメントツリー - 取得
int
fSegTGetOne(
	int piGetNo					// <I> 取得位置 0~
)
{
	// 現在範囲
	int liNNo = 1;
	int liNowS = 0;
	int liNowE = siSCNo - 1;

	// 取得位置へ移動
	while (liNowS != liNowE) {

		// 子に展開
		fSegTExt(liNNo);

		// 中間位置
		int liNowC = liNowS + (liNowE - liNowS) / 2;

		// 次の位置へ
		if (piGetNo <= liNowC) {
			liNNo = liNNo * 2;
			liNowE = liNowC;
		}
		else {
			liNNo = liNNo * 2 + 1;
			liNowS = liNowC + 1;
		}
	}

	// 取得
	return si1SegT[liNNo];
}

// 実行メイン
long long
fMain(
)
{
	int i;
	char lc1Buf[1024];

	// 線数・頂点数 - 取得
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d", &siLCnt, &siVCnt);

	// 線 - 取得
	for (i = 0; i < siLCnt; i++) {
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d%d", &sz1Line[i].miSNo, &sz1Line[i].miENo);
		if (sz1Line[i].miSNo > sz1Line[i].miENo) {
			fSwap(&sz1Line[i].miSNo, &sz1Line[i].miENo);
		}
	}

	// 線 - ソート
	qsort(sz1Line, siLCnt, sizeof(Line), fSortFnc);

	// セグメントツリー - 子の開始位置 - セット
	fSegTSetCSNo(siVCnt);

	// 線 - 配置
	long long llCnt = 0;
	for (i = 0; i < siLCnt; i++) {

		// 線数
		int liCntS = fSegTGetOne(sz1Line[i].miSNo);
		int liCntE = fSegTGetOne(sz1Line[i].miENo);

		// 交点数 - 加算
		llCnt += abs(liCntS - liCntE);

		// 線 - 配置
		fSegTUpRng(sz1Line[i].miSNo, sz1Line[i].miENo, 1);
	}

	return llCnt;
}

// 1回実行
int
fOne(
)
{
	long long llRet;
	char lc1Buf[1024];

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

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

	// 実行メイン
	llRet = fMain();

	// 出力
	sprintf(lc1Buf, "%lld\n", llRet);
	fOut(lc1Buf);

	// 残データ有無
#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", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

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

	return 0;
}

0