結果

問題 No.318 学学学学学
ユーザー asugen0402
提出日時 2019-02-08 14:34:44
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 81 ms / 2,000 ms
コード長 8,584 bytes
コンパイル時間 1,258 ms
コンパイル使用メモリ 33,280 KB
実行使用メモリ 7,220 KB
最終ジャッジ日時 2024-06-22 18:47:37
合計ジャッジ時間 3,918 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
// 内部定数
#define D_ARRAY_MAX     100000                                  // 最大配列数
#define D_SEGT_CNT      131072                                  // セグメントツリーデータ数(2の累乗)
#define D_SEGT_INI      0                                       // セグメントツリー初期値
#define D_TREE_MAX      D_ARRAY_MAX                             // 木の最大データ数
#define D_TREE_WCNT     2                                       // 木の方向数
#define D_TREE_LEFT     0                                       // 木の方向 - 左側
#define D_TREE_RIGHT    1                                       // 木の方向 - 右側
// 内部構造体 - 木構造
typedef struct Tree {
    int miVal;                                                  // 値
    int miMin;                                                  // 最小位置
    int miMax;                                                  // 最大位置
    int mi1Height[D_TREE_WCNT];                                 // 木の高さ
    struct Tree *mzp1Child[D_TREE_WCNT];                        // 子
} Tree;
// 内部変数
static FILE *szpFpI;                                            // 入力
static int si1Array[D_ARRAY_MAX];                               // 配列
static int siACnt;                                              // 配列数
static int si1SegT[D_SEGT_CNT * 2];                             // セグメントツリー
static Tree sz1Tree[D_TREE_MAX];                                // 木の実データ
static int siTCnt;                                              // 木の実データ数
static Tree *szpTop;                                            // 先頭の木データ
// セグメントツリー - 更新
int
fSegTUp(
    int piUpS                   // <I> 更新範囲 - 開始 0～
    , int piUpE                 // <I> 更新範囲 - 終了 0～
    , int piUpVal               // <I> 更新値
    , int piSNo                 // <I> セグメント木の配列番号 1～
    , int piSCrgS               // <I> セグメント木の担当範囲 - 開始 0～
    , int piSCrgE               // <I> セグメント木の担当範囲 - 終了 0～
)
{
    // 範囲外チェック
    if (piUpE < piSCrgS || piSCrgE < piUpS) {
        return 0;
    }
    // 範囲内チェック
    if (piUpS <= piSCrgS && piSCrgE <= piUpE) {
        si1SegT[piSNo] = piUpVal;                           // 更新
        return 0;
    }
    // 更新済みの場合、子に展開しておく
    if (si1SegT[piSNo] != D_SEGT_INI) {                 // 更新済み
        si1SegT[piSNo * 2] = si1SegT[piSNo];
        si1SegT[piSNo * 2 + 1] = si1SegT[piSNo];
        si1SegT[piSNo] = D_SEGT_INI;                        // 自分を初期化
    }
    // 範囲の半分
    int liHalf = (piSCrgE - piSCrgS + 1) / 2;
    // 両側の子へ
    fSegTUp(piUpS, piUpE, piUpVal, piSNo * 2, piSCrgS, piSCrgS + liHalf - 1);
    fSegTUp(piUpS, piUpE, piUpVal, piSNo * 2 + 1, piSCrgE - liHalf + 1, piSCrgE);
    return 0;
}
// セグメントツリー - 取得
int
fSegTGet(
    int piSNo                   // <I> セグメント木の配列番号 1～
)
{
    int liRet;
    // 初期値
    liRet = si1SegT[piSNo];
    // 親に値があれば更新
    while (piSNo > 1) {
        piSNo /= 2;                             // 上位へ
        if (si1SegT[piSNo] != D_SEGT_INI) {     // 更新済み
            liRet = si1SegT[piSNo];
        }
    }
    return liRet;
}
// 木データ - 作成
Tree *
fTreeMake(
    int piVal                   // <I> 値
    , int piNo                  // <I> 位置
)
{
    // 対象の木データ
    Tree *lzpTree = &(sz1Tree[siTCnt]);
    siTCnt++;
    // データセット
    memset(lzpTree, 0, sizeof(Tree));       // 初期化
    lzpTree->miVal = piVal;                 // 値
    lzpTree->miMin = piNo;                  // 最小位置
    lzpTree->miMax = piNo;                  // 最大位置
    return lzpTree;
}
// 木データ - 比較 - 値昇順
int
fTreeCmp(
    Tree *pzpTree               // <I> 木データ
    , int piVal                 // <I> 値
)
{
    // 値昇順
    if (piVal < pzpTree->miVal) {           // 左側
        return -1;
    }
    else if (piVal > pzpTree->miVal) {      // 右側
        return 1;
    }
    return 0;
}
// 木データ - 高さ取得
int
fTreeGetHeight(
    Tree *pzpTree               // <I> 対象の木情報
)
{
    // データ有無
    if (pzpTree == NULL) {
        return 0;
    }
    if (pzpTree->mi1Height[D_TREE_LEFT] >= pzpTree->mi1Height[D_TREE_RIGHT]) {
        return pzpTree->mi1Height[D_TREE_LEFT] + 1;
    }
    else {
        return pzpTree->mi1Height[D_TREE_RIGHT] + 1;
    }
}
// 木データ - 右回転(親は子の右下へ・子は親の左上へ)
int
fTreeRttR(
    Tree **pzppTree             // <I> 回転対象
)
{
    // 現在の子
    Tree *lzpChild = (*pzppTree)->mzp1Child[D_TREE_LEFT];
    // 右回転
    (*pzppTree)->mzp1Child[D_TREE_LEFT] = lzpChild->mzp1Child[D_TREE_RIGHT];    // 親の左側 = 子の右側
    (*pzppTree)->mi1Height[D_TREE_LEFT] = lzpChild->mi1Height[D_TREE_RIGHT];    // 親の高さ(左) = 子の高さ(右)
    lzpChild->mzp1Child[D_TREE_RIGHT] = *pzppTree;                              // 子の右側 = 親
    lzpChild->mi1Height[D_TREE_RIGHT] = fTreeGetHeight(*pzppTree);              // 子の高さ(右) - 親の高さ
    *pzppTree = lzpChild;                                                       // 親 = 子
    return 0;
}
// 木データ - 左回転(親は子の左下へ・子は親の右上へ)
int
fTreeRttL(
    Tree **pzppTree             // <I> 回転対象
)
{
    // 現在の子
    Tree *lzpChild = (*pzppTree)->mzp1Child[D_TREE_RIGHT];
    // 左回転
    (*pzppTree)->mzp1Child[D_TREE_RIGHT] = lzpChild->mzp1Child[D_TREE_LEFT];    // 親の右側 = 子の左側
    (*pzppTree)->mi1Height[D_TREE_RIGHT] = lzpChild->mi1Height[D_TREE_LEFT];    // 親の高さ(右) = 子の高さ(左)
    lzpChild->mzp1Child[D_TREE_LEFT] = *pzppTree;                               // 子の左側 = 親
    lzpChild->mi1Height[D_TREE_LEFT] = fTreeGetHeight(*pzppTree);               // 子の高さ(左) - 親の高さ
    *pzppTree = lzpChild;                                                       // 親 = 子
    return 0;
}
// 木データ - 追加・削除の共通処理
// 戻り値：[1]高さの変更あり [0]高さの変更なし
int
fTreeComAddDel(
    Tree **pzppNow              // <I> 現在の木情報
    , int piWay                 // <I> 対象の方向
)
{
    // 高さの変更があるかチェック
    int liNew = fTreeGetHeight((*pzppNow)->mzp1Child[piWay]);
    if ((*pzppNow)->mi1Height[piWay] == liNew) {                                                // 変化なし
        return 0;
    }
    (*pzppNow)->mi1Height[piWay] = liNew;                                                       // 更新
    // 高さが離れている場合、回転
    if ((*pzppNow)->mi1Height[D_TREE_LEFT] - (*pzppNow)->mi1Height[D_TREE_RIGHT] > 1) {         // 左側が高い
        fTreeRttR(pzppNow);                                                                         // 右回転
    }
    else if ((*pzppNow)->mi1Height[D_TREE_RIGHT] - (*pzppNow)->mi1Height[D_TREE_LEFT] > 1) {    // 右側が高い
        fTreeRttL(pzppNow);                                                                         // 左回転
    }
    return 1;
}
// 木データ - 追加
// 戻り値：[1]高さの変更あり [0]高さの変更なし [-1]追加なし
int
fTreeAdd(
    Tree **pzppNow              // <I> 現在の木情報
    , int piVal                 // <I> 値
    , int piNo                  // <I> 位置
)
{
    // 作成
    if (*pzppNow == NULL) {
        *pzppNow = fTreeMake(piVal, piNo);
        return 1;
    }
    // 比較
    int liRet = fTreeCmp(*pzppNow, piVal);
    // 一致
    if (liRet == 0) {
        (*pzppNow)->miMax = piNo;                                           // 最大位置 - 更新
        return -1;
    }
    // 方向の判別
    int liWay;
    if (liRet < 0) {                                                    // 左側
        liWay = D_TREE_LEFT;
    }
    else {                                                              // 右側
        liWay = D_TREE_RIGHT;
    }
    // 下位へ
    liRet = fTreeAdd(&((*pzppNow)->mzp1Child[liWay]), piVal, piNo);
    if (liRet < 1) {                                                    // 高さの変更なし or 追加なし
        return liRet;
    }
    // 追加・削除の共通処理
    return fTreeComAddDel(pzppNow, liWay);
}
// 木データ - 全データのループ
int
fTreeAll(
    Tree *pzpNow                // <I> 現在の木情報
)
{
    // データ有無
    if (pzpNow == NULL) {
        return 0;
    }
    // 左側
    fTreeAll(pzpNow->mzp1Child[D_TREE_LEFT]);
    // セグメントツリー - 更新
    fSegTUp(pzpNow->miMin, pzpNow->miMax, pzpNow->miVal, 1, 0, D_SEGT_CNT - 1);
    // 右側
    fTreeAll(pzpNow->mzp1Child[D_TREE_RIGHT]);
    return 0;
}
// 実行メイン
int
fMain(
    int piTNo                   // <I> テスト番号 1～
)
{
    int i;
    char lc1Buf[1024];
    // データ - 初期化
    memset(si1SegT, 0, sizeof(si1SegT));                        // セグメントツリー
    siTCnt = 0;                                                 // 木の実データ数
    szpTop = NULL;                                              // 先頭の木データ
    // 入力 - セット
#ifdef D_TEST
    sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);
    szpFpI = fopen(lc1Buf, "r");
#else
    szpFpI = stdin;
#endif
    // 配列数 - 取得
    fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
    sscanf(lc1Buf, "%d", &siACnt);
    // 配列 - 取得
    for (i = 0; i < siACnt; i++) {
        int liVal;
        fscanf(szpFpI, "%d", &liVal);
        // 木 - 追加
        fTreeAdd(&szpTop, liVal, i);
    }
    fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
    // 木の数でループ
    fTreeAll(szpTop);
    // セグメントツリー - 取得
    for (i = 0; i < siACnt; i++) {
        si1Array[i] = fSegTGet(D_SEGT_CNT + i);
    }
    // 結果 - １つ目
    printf("%d", si1Array[0]);
    // 結果 - ２つ目以降
    for (i = 1; i < siACnt; i++) {
        printf(" %d", si1Array[i]);
    }
    // 改行
    printf("\n");
    // テストファイルクローズ
#ifdef D_TEST
    fclose(szpFpI);
#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0