#347093 (C) No.789 範囲の合計

提出ソース

結果

問題	No.789 範囲の合計
ユーザー	asugen0402
提出日時	2019-05-16 17:21:48
言語	C (gcc 12.3.0)
結果	AC
実行時間	116 ms / 1,000 ms
コード長	6,557 bytes
コンパイル時間	573 ms
コンパイル使用メモリ	32,940 KB
実行使用メモリ	6,492 KB
最終ジャッジ日時	2023-10-17 06:58:55
合計ジャッジ時間	2,771 ms
ジャッジサーバーID （参考情報）	judge11 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,672 KB
testcase_01	AC	2 ms 4,672 KB
testcase_02	AC	107 ms 6,492 KB
testcase_03	AC	69 ms 6,492 KB
testcase_04	AC	100 ms 6,492 KB
testcase_05	AC	79 ms 6,492 KB
testcase_06	AC	86 ms 6,492 KB
testcase_07	AC	61 ms 6,492 KB
testcase_08	AC	71 ms 6,492 KB
testcase_09	AC	67 ms 6,492 KB
testcase_10	AC	116 ms 6,492 KB
testcase_11	AC	93 ms 6,492 KB
testcase_12	AC	92 ms 6,492 KB
testcase_13	AC	2 ms 4,672 KB
testcase_14	AC	2 ms 4,672 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

// 内部定数
#define D_QUERY_MAX		100000									// 最大クエリ数
#define D_ARRAY_MAX		D_QUERY_MAX * 2							// 最大配列数
#define D_SEGT_CNT		262144									// セグメントツリーデータ数(2の累乗)

// 内部構造体 - クエリ情報
typedef struct Query {
	int miMode;													// 0 or 1
	int miVal1, miVal2;											// 値
} Query;

// 内部変数
static FILE *szpFpI;											// 入力
static Query sz1Query[D_QUERY_MAX];								// クエリ
static int siQCnt;												// クエリ数
static int si1Array[D_ARRAY_MAX];								// 配列
static int siACnt;												// 配列数
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> １行
)
{
	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
fSortFnc(
	const void *pzpVal1			// <I> 値１
	, const void *pzpVal2		// <I> 値２
)
{
	int *lipVal1 = (int *)pzpVal1;
	int *lipVal2 = (int *)pzpVal2;

	// int昇順
	if (*lipVal1 > *lipVal2) {
		return 1;
	}
	else if (*lipVal1 < *lipVal2) {
		return -1;
	}

	return 0;
}

// 配列 - 重複カット
int
fCutDpl(
	int *pipArray				// <IO> 配列
	, int *pipACnt				// <IO> 配列数
)
{
	int i;
	int liTo = 1;
	int liDCnt = 0;
	for (i = 1; i < *pipACnt; i++) {
		if (pipArray[i] != pipArray[liTo - 1]) {
			pipArray[liTo] = pipArray[i];
			liTo++;
		}
		else {
			liDCnt++;
		}
	}

	*pipACnt -= liDCnt;

	return 0;
}

// 検索
// 戻り値：[>=0]配列番号 [-1]なし
int
fBSrh(
	int piVal					// <I> 値
	, int *pipArray				// <I> 配列
	, int piACnt				// <I> 配列数
)
{
	// 初期範囲
	int liSNo = 0;
	int liENo = piACnt - 1;

	// 検索
	while (1) {

		// 中間位置
		int liMNo = (liSNo + liENo) / 2;

		// 一致チェック
		if (piVal == pipArray[liMNo]) {
			return liMNo;
		}

		// 範囲を絞る
		if (piVal < pipArray[liMNo]) {				// 左側へ
			liENo = liMNo - 1;
		}
		else {										// 右側へ
			liSNo = liMNo + 1;
		}

		// 範囲チェック
		if (liSNo > liENo) {
			return -1;
		}
	}

	return -1;
}

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

	return 0;
}

// セグメントツリー - 子の処理
int
fSegTCProc(
	int piNo1					// <I> 位置１ 0～
	, int piNo2					// <I> 位置２ 0～
)
{
	return si1SegT[piNo1] + si1SegT[piNo2];
}

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

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

	int liRet = 0;

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

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

	return liRet;
}
int
fSegTGetRng(
	int piGetS					// <I> 取得範囲 - 開始 0～
	, int piGetE				// <I> 取得範囲 - 終了 0～
)
{
	return fSegTGetRngMain(piGetS, piGetE, 1, 0, siSCNo - 1);
}

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

	// 更新
	si1SegT[liCNo1] += piAdd;

	// 親を更新
	while (1) {

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

		// 更新
		si1SegT[liPNo] = fSegTCProc(liCNo1, liCNo2);

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

	return 0;
}

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

	// クエリ数・配列数 - 取得
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d", &siQCnt);
	siACnt = siQCnt * 2;

	// クエリ・配列 - 取得
	for (i = 0; i < siQCnt; i++) {
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d%d%d", &sz1Query[i].miMode, &sz1Query[i].miVal1, &sz1Query[i].miVal2);
		si1Array[i * 2] = sz1Query[i].miVal1;
		si1Array[i * 2 + 1] = sz1Query[i].miVal2;
	}

	// 配列 - ソート
	qsort(si1Array, siACnt, sizeof(int), fSortFnc);

	// 配列 - 重複カット
	fCutDpl(si1Array, &siACnt);

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

	// クエリ - 実行
	long long llSum = 0;
	for (i = 0; i < siQCnt; i++) {
		int liNo1 = fBSrh(sz1Query[i].miVal1, si1Array, siACnt);
		if (sz1Query[i].miMode == 0) {
			fSegTUpOne(liNo1, sz1Query[i].miVal2);
		}
		else {
			int liNo2 = fBSrh(sz1Query[i].miVal2, si1Array, siACnt);
			llSum += fSegTGetRng(liNo1, liNo2);
		}
	}

	return llSum;
}

// １回実行
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;
}

yukicoder

結果

テストケース

ソースコード