結果

問題 No.318 学学学学学
ユーザー aketijyuuzou
提出日時 2024-10-10 20:49:41
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 361 ms / 2,000 ms
コード長 8,159 bytes
コンパイル時間 8,211 ms
コンパイル使用メモリ 170,752 KB
実行使用メモリ 190,228 KB
最終ジャッジ日時 2024-10-10 20:49:57
合計ジャッジ時間 15,348 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (97 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/

ソースコード

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

using System;
using System.Collections.Generic;
using System.Linq;
class 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));
}
}
#region LazySegmentTree
// LazySegmentTree (RMQ and RUQ)
internal class LazySegmentTree
{
private int[] mTreeNodeArr;
private int UB; // UB
private 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;
// OverLapint.MaxValue
if (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]);
}
}
}
}
#endregion
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0