結果

問題 No.743 Segments on a Polygon
ユーザー asugen0402asugen0402
提出日時 2019-05-16 11:01:22
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 109 ms / 2,000 ms
コード長 5,607 bytes
コンパイル時間 1,698 ms
コンパイル使用メモリ 32,768 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-17 05:26:53
合計ジャッジ時間 3,376 ms
ジャッジサーバーID
(参考情報)
judge5 / judge6
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

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>
)
{
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>
, int *pipVal2 // <IO>
)
{
int liWork = *pipVal1;
*pipVal1 = *pipVal2;
*pipVal2 = liWork;
return 0;
}
// -
int
fSortFnc(
const void *pzpVal1 // <I>
, const void *pzpVal2 // <I>
)
{
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;
}
//
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0