結果
| 問題 | No.318 学学学学学 |
| ユーザー |
 明智重蔵
|
| 提出日時 | 2021-11-07 09:53:08 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 364 ms / 2,000 ms |
| コード長 | 8,129 bytes |
| コンパイル時間 | 7,939 ms |
| コンパイル使用メモリ | 167,212 KB |
| 実行使用メモリ | 189,648 KB |
| 最終ジャッジ日時 | 2024-11-08 20:33:37 |
| 合計ジャッジ時間 | 16,040 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (99 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;using System.Collections.Generic;using System.Linq;// https://yukicoder.me/problems/no/318class Program{static string InputPattern = "InputX";static List<string> GetInputList(){var WillReturn = new List<string>();if (InputPattern == "Input1") {WillReturn.Add("6");WillReturn.Add("3 2 1 1 2 3");//3 3 3 3 3 3}else if (InputPattern == "Input2") {WillReturn.Add("6");WillReturn.Add("3 1 10 3 10 2");//3 3 10 10 10 2}else if (InputPattern == "Input3") {WillReturn.Add("6");WillReturn.Add("1 3 10 1 10 2");//1 3 10 10 10 2}else {string wkStr;while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);}return WillReturn;}class RangeInfoDef{internal int RangeSta;internal int RangeEnd;}static void Main(){List<string> InputList = GetInputList();int[] AArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();int LeafCnt = AArr.Length;var InsLazySegmentTree = new LazySegmentTree(LeafCnt);var RangeDict = new Dictionary<int, RangeInfoDef>();for (int I = 0; I <= AArr.GetUpperBound(0); I++) {if (RangeDict.ContainsKey(AArr[I]) == false) {RangeDict[AArr[I]] = new RangeInfoDef();RangeDict[AArr[I]].RangeSta = I;}RangeDict[AArr[I]].RangeEnd = I;}foreach (var EachPair in RangeDict.OrderBy(pX => pX.Key)) {InsLazySegmentTree.RangeUpdate(EachPair.Value.RangeSta, EachPair.Value.RangeEnd, EachPair.Key, 0);}var AnswerList = new List<int>();for (int I = 0; I <= AArr.GetUpperBound(0); I++) {int MinVal = InsLazySegmentTree.Query(I, I, 0);AnswerList.Add(MinVal);}string[] AnswerArr = Array.ConvertAll(AnswerList.ToArray(), pX => pX.ToString());Console.WriteLine(string.Join(" ", AnswerArr));}}// LazySegmentTreeクラスinternal class LazySegmentTree{private int[] mTreeNodeArr;private int UB; // 木のノードの配列のUBprivate int mLeafCnt; // 葉ノードの数private int?[] mLazyArr; // 遅延配列// ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列private struct RangeInfoDef{internal int StaInd;internal int EndInd;}private RangeInfoDef[] mRangeInfo;// コンストラクタinternal LazySegmentTree(int pLeafCnt){// 簡単のため、葉ノード数を2のべき乗にint ArrLength = 0;for (int I = 1; I < int.MaxValue; I *= 2) {ArrLength += I;mLeafCnt = I;if (pLeafCnt < mLeafCnt) break;}// すべての値をint.MaxValueにUB = ArrLength - 1;mTreeNodeArr = new int[UB + 1];for (int I = 0; I <= UB; I++) {mTreeNodeArr[I] = int.MaxValue;}// 遅延配列を初期化mLazyArr = new int?[UB + 1];// ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列の作成mRangeInfo = new RangeInfoDef[UB + 1];for (int I = 0; I <= UB; I++) {if (I == 0) {RangeInfoDef WillSet1;WillSet1.StaInd = 0;WillSet1.EndInd = mLeafCnt - 1;mRangeInfo[I] = WillSet1;continue;}int ParentNode = DeriveParentNode(I);RangeInfoDef ParentRangeInfo = mRangeInfo[ParentNode];RangeInfoDef WillSet2;int Mid = (ParentRangeInfo.StaInd + ParentRangeInfo.EndInd) / 2;if (I % 2 == 1) { // 奇数ノードの場合WillSet2.StaInd = ParentRangeInfo.StaInd;WillSet2.EndInd = Mid;}else { // 偶数ノードの場合WillSet2.StaInd = Mid + 1;WillSet2.EndInd = ParentRangeInfo.EndInd;}mRangeInfo[I] = WillSet2;}}// 親ノードの添字を取得private int DeriveParentNode(int pTarget){return (pTarget - 1) / 2;}// 子ノードの添字(小さいほう)を取得private int DeriveChildNode(int pTarget){return pTarget * 2 + 1;}// カレントノードを引数として、遅延評価を行うvoid LazyEval(int pCurrNode){// 遅延配列が空なら何もしないif (mLazyArr[pCurrNode].HasValue == false) return;// 遅延配列の値を反映するmTreeNodeArr[pCurrNode] = mLazyArr[pCurrNode].Value;int ChildNode1 = DeriveChildNode(pCurrNode);int ChildNode2 = ChildNode1 + 1;if (ChildNode1 <= UB) {mLazyArr[ChildNode1] = mLazyArr[pCurrNode].Value;}if (ChildNode2 <= UB) {mLazyArr[ChildNode2] = mLazyArr[pCurrNode].Value;}// 伝播が終わったので、自ノードの遅延配列を空にするmLazyArr[pCurrNode] = null;}// 開始添字と終了添字とカレントノードを引数として、区間更新を行うinternal void RangeUpdate(int pSearchStaInd, int pSearchEndInd, int pUpdateVal, int pCurrNode){// カレントノードの遅延評価を行うLazyEval(pCurrNode);int CurrNodeStaInd = mRangeInfo[pCurrNode].StaInd;int CurrNodeEndInd = mRangeInfo[pCurrNode].EndInd;// OverLapしてなければ、何もしないif (CurrNodeEndInd < pSearchStaInd || pSearchEndInd < CurrNodeStaInd) {return;}// 完全に含んでいれば、遅延配列に値を入れた後に評価if (pSearchStaInd <= CurrNodeStaInd && CurrNodeEndInd <= pSearchEndInd) {mLazyArr[pCurrNode] = pUpdateVal;LazyEval(pCurrNode);return;}// そうでなければ、2つの区間に再帰呼出しint ChildNode1 = DeriveChildNode(pCurrNode);int ChildNode2 = ChildNode1 + 1;RangeUpdate(pSearchStaInd, pSearchEndInd, pUpdateVal, ChildNode1);RangeUpdate(pSearchStaInd, pSearchEndInd, pUpdateVal, ChildNode2);// カレントノードの更新mTreeNodeArr[pCurrNode] = Math.Min(mTreeNodeArr[ChildNode1], mTreeNodeArr[ChildNode2]);}// 開始添字と終了添字とカレントノードを引数として、最小値を返すinternal int Query(int pSearchStaInd, int pSearchEndInd, int pCurrNode){// 該当ノードを遅延評価するLazyEval(pCurrNode);int CurrNodeStaInd = mRangeInfo[pCurrNode].StaInd;int CurrNodeEndInd = mRangeInfo[pCurrNode].EndInd;// OverLapしてなければ、int.MaxValueif (CurrNodeEndInd < pSearchStaInd || pSearchEndInd < CurrNodeStaInd)return int.MaxValue;// 完全に含んでいれば、このノードの値if (pSearchStaInd <= CurrNodeStaInd && CurrNodeEndInd <= pSearchEndInd)return mTreeNodeArr[pCurrNode];// そうでなければ、2つの子の最小値int ChildNode1 = DeriveChildNode(pCurrNode);int ChildNode2 = ChildNode1 + 1;int ChildVal1 = Query(pSearchStaInd, pSearchEndInd, ChildNode1);int ChildVal2 = Query(pSearchStaInd, pSearchEndInd, ChildNode2);return Math.Min(ChildVal1, ChildVal2);}internal void DebugPrint(){for (int I = 0; I <= UB; I++) {if (mLazyArr[I].HasValue) {Console.WriteLine("mTreeNodeArr[{0}] = {1} , mLazyArr[{0}] = {2}", I, mTreeNodeArr[I], mLazyArr[I]);}else {Console.WriteLine("mTreeNodeArr[{0}] = {1}", I, mTreeNodeArr[I]);}}}}