結果
| 問題 |
No.1824 門＼松＼列
|
| コンテスト | |
| ユーザー |
 chikara-miki
|
| 提出日時 | 2022-02-12 22:57:44 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 98 ms / 2,000 ms |
| コード長 | 35,301 bytes |
| コンパイル時間 | 15,871 ms |
| コンパイル使用メモリ | 171,084 KB |
| 実行使用メモリ | 210,032 KB |
| 最終ジャッジ日時 | 2024-06-29 02:12:06 |
| 合計ジャッジ時間 | 15,372 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 4 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /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/
ソースコード
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Xml.Xsl;
using System.Reflection;
using System.Diagnostics;
using System.Collections;
namespace Atcoder
{
public class Program
{
static void Main(string[] args)
{
var T = GetInt();
var map = new List<long>();
map.Add(0);
map.Add(0);
for (long i = 2; i <= 1000000; i++)
{
map.Add(i * i - 3 * i + 2);
map[(int)i] += map[(int)i - 1];
}
for (int i = 0; i < T; i++)
{
var tmp = GetInt();
Console.WriteLine(map[tmp] * 2);
}
}
public class CID
{
//OrderBy シーケンスの要素をキーに従って昇順に並べ替えます。
//OrderByDescending シーケンスの要素をキーに従って降順に並べ替えます。
//ThenBy キーに従って昇順のシーケンス内の要素の後続の並べ替えを実行します。
//ThenByDescending キーに従って降順に並べ替え、シーケンス内の要素の後続の並べ替えを実行します。
public CID(int l, int r)
{
L = l;
R = r;
}
public int L { get; set; }
public int R { get; set; }
}
#region よく使う定数
public static long INF = 1000000007;
public static string FILLVALUE = "000000";
//上→右→下→左
public static int[] dx = new int[] { 0, 1, 0, -1 };
public static int[] dy = new int[] { -1, 0, 1, 0 };
#endregion
#region 良く使う関数
/// <summary>
/// 文字で埋める
/// </summary>
/// <param name="val">値</param>
/// <returns></returns>
static string Fill(long val)
{
return $"{val:FILLVALUE}";
}
/// <summary>
/// ファイル出力
/// </summary>
/// <param name="path">出力先</param>
/// <param name="append">false：上書き true：追加</param>
/// <param name="text">内容</param>
static void OutputFile(bool append, string text)
{
var path = "C:\\Users\\cmiki\\Desktop\\output.txt";
using (StreamWriter writer = new StreamWriter(path, append))
{
writer.WriteLine(text);
}
}
/// <summary>
/// ファイルから取得
/// </summary>
/// <param name="path">ファイルパス</param>
/// <returns></returns>
static List<List<int>> InputFile(string path)
{
var ret = new List<List<int>>();
StreamReader sr = new StreamReader(path);
string line = null;
while ((line = sr.ReadLine()) != null)
{
ret.Add(line.Split(' ').Select(i => int.Parse(i)).ToList());
}
if (sr != null)
{
sr.Close();
}
return ret;
}
/// <summary>
/// 値から全パターン出力(何回使ってもOK)
/// </summary>
/// <param name="val">今の値</param>
/// <param name="item">ベースのリスト</param>
/// <param name="ans">戻すリスト</param>
/// <param name="len">何桁までやるか</param>
/// <returns></returns>
static List<string> AllPattern(string val, List<char> items, List<string> ans, long N)
{
if (val.Length == N)
{
ans.Add(val);
return ans;
}
foreach (var item in items)
{
AllPattern(val + item, items, ans, N);
}
return ans;
}
/// <summary>
/// 値から全パターン出力(1回のみ)
/// </summary>
/// <param name="val">今の値</param>
/// <param name="item">ベースのリスト</param>
/// <param name="ans">戻すリスト</param>
/// <param name="len">何桁までやるか</param>
/// <param name="con">使ったかのフラグ</param>
/// <returns></returns>
static SortedSet<string> NoCoverPattern(string val, List<string> items, SortedSet<string> ans, int len, List<bool> con)
{
// 桁数に応じて変える
if (val.Length == len)
{
ans.Add(val);
return ans;
}
for (int i = 0; i < items.Count; i++)
{
if (con[i])
{
con[i] = false;
NoCoverPattern(val + items[i], items, ans, len, con);
con[i] = true;
}
}
return ans;
}
#endregion
#region 値取得
#region string
static string GetString()
{
return Console.ReadLine();
}
static string[] GetStringArray()
{
return Console.ReadLine().Split(' ').ToArray();
}
static List<string> GetStringList()
{
return Console.ReadLine().Split(' ').ToList();
}
static List<string> GetStringRepeat(string val, int cnt)
{
return Enumerable.Repeat(val, cnt).ToList();
}
static string[,] GetStringArrayHW(int H, int W)
{
var ret = new string[H, W];
for (int i = 0; i < H; i++)
{
var tmp = GetStringArray();
for (int j = 0; j < W; j++)
{
ret[i, j] = tmp[j];
}
}
return ret;
}
#endregion
#region int
static int GetInt()
{
return int.Parse(Console.ReadLine());
}
static int[] GetIntArray()
{
return Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
}
static List<int> GetIntList()
{
return Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToList();
}
static List<int> GetIntRepeat(int val, int cnt)
{
return Enumerable.Repeat(val, cnt).ToList();
}
static List<List<int>> GetIntListList(int N)
{
var ret = new List<List<int>>();
for (int i = 0; i < N; i++)
{
var tmp = GetIntList();
ret.Add(tmp);
}
return ret;
}
static int[,] GetIntArrayHW(int H, int W)
{
var ret = new int[H, W];
for (int i = 0; i < H; i++)
{
var tmp = GetIntArray();
for (int j = 0; j < W; j++)
{
ret[i, j] = tmp[j];
}
}
return ret;
}
#endregion
#region BigIntger
static BigInteger GetBigInt()
{
return BigInteger.Parse(Console.ReadLine());
}
static BigInteger[] GetBigIntArray()
{
return Console.ReadLine().Split(' ').Select(i => BigInteger.Parse(i)).ToArray();
}
#endregion
#region long
static long GetLong()
{
return long.Parse(Console.ReadLine());
}
static long[] GetLongArray()
{
return Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
}
static List<long> GetLongList()
{
return Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToList();
}
static List<long> GetLongRepeat(long val, int cnt)
{
return Enumerable.Repeat(val, cnt).ToList();
}
static List<List<long>> GetLongListList(long N)
{
var ret = new List<List<long>>();
for (long i = 0; i < N; i++)
{
var tmp = GetLongList();
ret.Add(tmp);
}
return ret;
}
static long[,] GetLongArrayHW(long H, long W)
{
var ret = new long[H, W];
for (long i = 0; i < H; i++)
{
var tmp = GetLongArray();
for (int j = 0; j < W; j++)
{
ret[i, j] = tmp[j];
}
}
return ret;
}
#endregion
#region double
static double GetDouble()
{
return double.Parse(Console.ReadLine());
}
static double[] GetDoubleArray()
{
return Console.ReadLine().Split(' ').Select(i => double.Parse(i)).ToArray();
}
static List<double> GetDoubleList()
{
return Console.ReadLine().Split(' ').Select(i => double.Parse(i)).ToList();
}
static List<double> GetDoubleRepeat(double val, int cnt)
{
return Enumerable.Repeat(val, cnt).ToList();
}
#endregion
#region decimal
static decimal GetDecimal()
{
return decimal.Parse(Console.ReadLine());
}
static decimal[] GetDecimalArray()
{
return Console.ReadLine().Split(' ').Select(i => decimal.Parse(i)).ToArray();
}
static List<decimal> GetDecimalList()
{
return Console.ReadLine().Split(' ').Select(i => decimal.Parse(i)).ToList();
}
static List<decimal> GetDecimalRepeat(decimal val, int cnt)
{
return Enumerable.Repeat(val, cnt).ToList();
}
#endregion
#region bool
static List<bool> GetBoolRepeat(bool val, int cnt)
{
return Enumerable.Repeat(val, cnt).ToList();
}
static List<List<bool>> GetBoolRepeatHW(bool val, int H, int W)
{
var ret = new List<List<bool>>();
for (int i = 0; i < H; i++)
{
var tmp = Enumerable.Repeat(val, W).ToList();
ret.Add(tmp);
}
return ret;
}
#endregion
#endregion
#region 公式等
/// <summary>
/// 左辺と右辺のルートを外して整数で比較
/// </summary>
/// <param name="a">左辺１</param>
/// <param name="b">左辺２</param>
/// <param name="c">右辺</param>
/// <returns>右辺が大きい：true</returns>
public static bool RemoveRoot(long a,long b,long c)
{
/*
√a +√b < √c (1)
(√a +√b)^2 < c (2)
2√ab < c − a − b (3)
c − a − b > 0 ∧ 4ab < (c − a − b)^2
*/
var d = c - a - b;
return 0 < d && 4 * a * b < d * d;
}
/// <summary>
/// 串刺し問題は区間スケジューリング法
/// 右側で並び替えの右とって左を見る。
/// </summary>
public static void Skewers()
{
//この形
var ND = GetIntArray();
var N = ND[0];
var D = ND[1];
var LR = new List<CID>();
for (int i = 0; i < N; i++)
{
var tmp = GetIntArray();
var t = new CID(tmp[0], tmp[1]);
LR.Add(t);
}
LR = LR.OrderBy(x => x.R).ThenBy(x => x.L).ToList();
var cnt = 1;
var min = LR[0].R;
for (int i = 1; i < N; i++)
{
if (LR[i].L <= min + D - 1)
{
continue;
}
min = LR[i].R;
cnt++;
}
Console.WriteLine(cnt);
}
/// <summary>
/// 逆元
/// </summary>
/// <param name="a"></param>
/// <returns></returns>
public static long Inverse(long a)
{
return modpow(a, INF - 2);
}
/// <summary>
/// 本当の繰返二乗法
/// </summary>
/// <param name="a">選択肢が何通り有るか</param>
/// <param name="n">何個有るか</param>
/// <param name="mod"></param>
/// <returns></returns>
public static long modpow(long a, long n)
{
a %= INF;
long res = 1;
while (n > 0)
{
if ((n & 1) == 1)
res = (res * a) % INF;
a = (a * a) % INF;
n >>= 1;
}
return res;
}
/// <summary>
/// 指定進数から10進数に戻す
/// </summary>
/// <param name="val">元の値</param>
/// <param name="Num">変換元の進数(10進数以下)</param>
/// <returns></returns>
static long ChangDecimalnumber(long val, long Num)
{
long ans = 0;
var cnt = 0;
while (val != 0)
{
ans += ((val % 10) * (long)Math.Pow(Num, cnt));
val /= 10;
cnt++;
}
return ans;
}
/// <summary>
/// 10進数から指定進数に変換
/// </summary>
/// <param name="val">元の値</param>
/// <param name="Num">変換先の進数(10進数以下)</param>
/// <returns></returns>
static BigInteger ChangBaseNumber(BigInteger val, long Num)
{
if (val == 0)
return 0;
var li = new List<BigInteger>();
while (0 != val)
{
li.Add(val % Num);
val /= Num;
}
li.Reverse();
return BigInteger.Parse(string.Join("", li));
}
/// <summary>
/// エラトステネスの篩
/// </summary>
/// <param name="val">範囲の最大値</param>
/// <returns>true：素数 false：素数ではない</returns>
static List<bool> EratosthenesSieve(int val)
{
var dp = GetBoolRepeat(true, val + 1);
dp[0] = dp[1] = false;
var sq = (int)Math.Sqrt(val);
for (int i = 2; i <= sq; i++)
{
if (dp[i])
{
int n = i + i;
while (n <= val)
{
dp[n] = false;
n += i;
}
}
}
return dp;
}
/// <summary>
/// 各桁の和
/// </summary>
/// <param name="sum">合計</param>
/// <param name="val">値</param>
/// <returns></returns>
static long DigitSum(long sum, long val)
{
sum += val % 10;
val /= 10;
if (val == 0)
return sum;
else
return DigitSum(sum, val);
}
/// <summary>
/// 自然数の和
/// </summary>
/// <param name="num">最大数</param>
/// <returns>合計</returns>
static long Sumofnatural(long num)
{
return num * (num + 1) / 2;
}
/// <summary>
/// 文字入れ替え
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="t1"></param>
/// <param name="t2"></param>
/// Swap(ref s[i2][p1 - N], ref s[i2][p2 - N]);の形式で呼出
static void Swap<T>(ref T t1, ref T t2)
{
T t3 = t1;
t1 = t2;
t2 = t3;
}
/// <summary>
/// 回文チェック
/// </summary>
/// <param name="Target">文字列</param>
/// <param name="len">文字数</param>
/// <returns>true：回文 false：回文ではない</returns>
static bool PalindromeCheck(string Target)
{
var len = Target.Length;
for (int i = 0; i < len / 2; i++)
{
if (Target[i] != Target[len - 1 - i])
{
return (false);
}
}
return true;
}
/// <summary>
/// アナグラムチェック 文字列の文字の構成が同じか(文字を入れ替えた時に同一になるか)
/// </summary>
/// <param name="word1"></param>
/// <param name="word2"></param>
/// <returns>true：アナグラム false：アナグラムではない</returns>
static bool AnagramCheck(string word1, string word2)
{
char[] val1 = word1.ToCharArray();
char[] val2 = word2.ToCharArray();
Array.Sort(val1);
Array.Sort(val2);
word1 = new string(val1);
word2 = new string(val2);
return word1 == word2;
//return word1.OrderBy(x => x).SequenceEqual(word2.OrderBy(x => x));
}
/// <summary>
/// 最小公倍数
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns>最小公倍数</returns>
public static long Lcm(long a, long b)
{
return a * b / Gcd(a, b);
}
/// <summary>
/// 最大公約数
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns>最大公約数</returns>
public static long Gcd(long a, long b)
{
if (a < b)
// 引数を入替えて自分を呼び出す
return Gcd(b, a);
while (b != 0)
{
var remainder = a % b;
a = b;
b = remainder;
}
return a;
}
/// <summary>
/// 余弦定理 三角形の2辺とその接点の角度から残りの辺の長さを出す。
/// </summary>
/// <param name="A">辺の長さ</param>
/// <param name="B">辺の長さ</param>
/// <param name="k">角度</param>
/// <returns>辺の長さ</returns>
public static double CosineTheorem(double A, double B, double k)
{
return Math.Sqrt(A * A + B * B - 2 * A * B * Math.Cos(Math.PI * k / 180));
}
/// <summary>
/// 正弦定理 外接円の半径と辺に対する角度から辺の長さを出す。※三角形
/// </summary>
/// <param name="R">円の半径</param>
/// <param name="k">角度</param>
/// <returns>辺の長さ</returns>
public static double SineTheorem(double R, double k)
{
return 2 * R * Math.Sin(k);
}
/// <summary>
/// ユークリッド距離
/// </summary>
/// <param name="x1">現在のx座標</param>
/// <param name="y1">現在のy座標</param>
/// <param name="x2">移動後のx座標</param>
/// <param name="y2">移動後のy座標</param>
/// <returns></returns>
public static double EuclideanDistance(double x1, double y1, double x2, double y2)
{
return Math.Sqrt(Math.Pow(x1 - x2, 2) + Math.Pow(y1 - y2, 2));
}
/// <summary>
/// 繰返二乗法っぽいやつ
/// </summary>
/// <param name="val">値</param>
/// <param name="div">割値</param>
/// <param name="minus">引値</param>
/// <returns></returns>
public static long RepeatedSquares(long val, long div, long minus)
{
if (val == 1)
return val;
if (val % div == 0)
{
RepeatedSquares(val / div, div, minus);
}
else
{
RepeatedSquares(val - minus, div, minus);
}
return val;
}
/// <summary>
/// 二分探索
/// </summary>
/// <param name="items">検索リスト</param>
/// <param name="target">検索対象</param>
/// <returns>自分以下_最大indexを返す</returns>
public static int BinarySearchNear(List<int> items, int target)
{
var min = 0;
var max = items.Count;
if (items[max - 1] < target)
return max - 1;
if (target < items[0])
return - 1;
while (min + 1 < max)
{
var mid = (min + max) / 2;
if (items[mid] <= target)
min = mid;
else
max = mid;
}
return min;
}
/// <summary>
/// 二分探索
/// </summary>
/// <param name="items"></param>
/// <param name="target"></param>
/// <returns>自分以上_最小indexを返す</returns>
public static int LowerBound(List<long> items, long target)
{
var min = -1;
var max = items.Count;
if (items[max - 1] < target)
return max;
if (target < items[0])
return 0;
while (min + 1 < max)
{
var mid = (min + max) / 2;
if (target <= items[mid])
max = mid;
else
min = mid;
}
return max;
}
/// <summary>
/// ３点の座標に囲まれた三角形の面積
/// </summary>
/// <param name="x1"></param>
/// <param name="y1"></param>
/// <param name="x2"></param>
/// <param name="y2"></param>
/// <param name="x3"></param>
/// <param name="y3"></param>
/// <returns></returns>
public static bool TriangleArea(double x1, double y1, double x2, double y2, double x3, double y3)
{
//var result = 0d;
var ln1 = LineLen(x1, y1, x2, y2);
var ln2 = LineLen(x2, y2, x3, y3);
var ln3 = LineLen(x3, y3, x1, y1);
var tmp = new List<double>();
tmp.Add(ln1);
tmp.Add(ln2);
tmp.Add(ln3);
tmp.Sort();
if (tmp[0] + tmp[1] <= tmp[2])
return false;
else
return true;
//ヘロンの公式
//s=(a+b+c)/2
//S=√s(s-a)(s-b)(s-c)
//var s1 = (ln1 + ln2 + ln3) / 2d;
//var s2 = s1 * (s1 - ln1) * (s1 - ln2) * (s1 - ln3);
//result = Math.Sqrt(s2);
//return result;
}
/// <summary>
/// ２点間の距離を返す
/// </summary>
/// <param name="x1"></param>
/// <param name="y1"></param>
/// <param name="x2"></param>
/// <param name="y2"></param>
/// <returns></returns>
public static double LineLen(double x1, double y1, double x2, double y2)
{
return Math.Sqrt(Math.Pow(Math.Abs(x1 - x2), 2.0f) + Math.Pow(Math.Abs(y1 - y2), 2.0f));
}
/// <summary>
/// 組合せの数(順序違いは数えない)
/// </summary>
/// <param name="n">何個中</param>
/// <param name="r">何個選ぶか</param>
/// <returns></returns>
public static Mint nCr(long n, long r)
{
var ret = new Mint(1);
for (long i = n - r + 1; i <= n; i++)
ret *= i;
for (int i = 2; i <= r; i++)
ret /= i;
return ret;
}
/// <summary>
/// 組合せの数(順序違いも数える)
/// </summary>
/// <param name="n">何個中</param>
/// <param name="r">何個選ぶか</param>
/// <returns></returns>
public static Mint nPr(long n, long r)
{
var ret = new Mint(1);
for (long i = n - r + 1; i <= n; i++)
ret *= i;
return ret;
}
#endregion
#region クラス
#region ユニオンファインド
public class UnionFind
{
// 親要素のインデックスを保持する
// 親要素が存在しない(自身がルートである)とき、マイナスでグループの要素数を持つ
public int[] Parents { get; set; }
public UnionFind(int n)
{
this.Parents = new int[n];
for (int i = 0; i < n; i++)
{
// 初期状態ではそれぞれが別のグループ(ルートは自分自身)
// ルートなのでマイナスで要素数(1個)を保持する
this.Parents[i] = -1;
}
}
// 要素xのルート要素はどれか
public int Find(int x)
{
// 親がマイナスの場合は自分自身がルート
if (this.Parents[x] < 0) return x;
// ルートが見つかるまで再帰的に探す
// 見つかったルートにつなぎかえる
this.Parents[x] = Find(this.Parents[x]);
return this.Parents[x];
}
// 要素xの属するグループの要素数を取得する
public int Size(int x)
{
// ルート要素を取得して、サイズを取得して返す
return -this.Parents[this.Find(x)];
}
// 要素x, yが同じグループかどうか判定する
public bool Same(int x, int y)
{
return this.Find(x) == this.Find(y);
}
// 要素x, yが属するグループを同じグループにまとめる
public bool Union(int x, int y)
{
// x, y のルート
x = this.Find(x);
y = this.Find(y);
// すでに同じグループの場合処理しない
if (x == y) return false;
// 要素数が少ないグループを多いほうに書き換えたい
if (this.Size(x) < this.Size(y))
{
var tmp = x;
x = y;
y = tmp;
}
// まとめる先のグループの要素数を更新
this.Parents[x] += this.Parents[y];
// まとめられるグループのルートの親を書き換え
this.Parents[y] = x;
return true;
}
}
#endregion
#region プライオリティキュー
public class PriorityQueue<T> : IEnumerable<T>
{
private readonly List<T> _data = new List<T>();
private readonly IComparer<T> _comparer;
private readonly bool _isDescending;
public PriorityQueue(IComparer<T> comparer, bool isDescending = true)
{
_comparer = comparer;
_isDescending = isDescending;
}
public PriorityQueue(Comparison<T> comparison, bool isDescending = true)
: this(Comparer<T>.Create(comparison), isDescending)
{
}
public PriorityQueue(bool isDescending = true)
: this(Comparer<T>.Default, isDescending)
{
}
public void Enqueue(T item)
{
_data.Add(item);
var childIndex = _data.Count - 1;
while (childIndex > 0)
{
var parentIndex = (childIndex - 1) / 2;
if (Compare(_data[childIndex], _data[parentIndex]) >= 0)
break;
Swap(childIndex, parentIndex);
childIndex = parentIndex;
}
}
public T Dequeue()
{
var lastIndex = _data.Count - 1;
var firstItem = _data[0];
_data[0] = _data[lastIndex];
_data.RemoveAt(lastIndex--);
var parentIndex = 0;
while (true)
{
var childIndex = parentIndex * 2 + 1;
if (childIndex > lastIndex)
break;
var rightChild = childIndex + 1;
if (rightChild <= lastIndex && Compare(_data[rightChild], _data[childIndex]) < 0)
childIndex = rightChild;
if (Compare(_data[parentIndex], _data[childIndex]) <= 0)
break;
Swap(parentIndex, childIndex);
parentIndex = childIndex;
}
return firstItem;
}
public T Peek()
{
return _data[0];
}
private void Swap(int a, int b)
{
var tmp = _data[a];
_data[a] = _data[b];
_data[b] = tmp;
}
private int Compare(T a, T b)
{
return _isDescending ? _comparer.Compare(b, a) : _comparer.Compare(a, b);
}
public int Count => _data.Count;
public IEnumerator<T> GetEnumerator()
{
return _data.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
public class PriorityQueue<TKey, TValue> : IEnumerable<TValue>
{
private readonly List<KeyValuePair<TKey, TValue>> _data = new List<KeyValuePair<TKey, TValue>>();
private readonly bool _isDescending;
private readonly Func<TValue, TKey> _keySelector;
private readonly IComparer<TKey> _keyComparer;
public PriorityQueue(Func<TValue, TKey> keySelector, bool isDescending = true)
: this(keySelector, Comparer<TKey>.Default, isDescending)
{
}
public PriorityQueue(Func<TValue, TKey> keySelector, IComparer<TKey> keyComparer, bool isDescending = true)
{
_keySelector = keySelector;
_keyComparer = keyComparer;
_isDescending = isDescending;
}
public void Enqueue(TValue item)
{
_data.Add(new KeyValuePair<TKey, TValue>(_keySelector(item), item));
var childIndex = _data.Count - 1;
while (childIndex > 0)
{
var parentIndex = (childIndex - 1) / 2;
if (Compare(_data[childIndex].Key, _data[parentIndex].Key) >= 0)
break;
Swap(childIndex, parentIndex);
childIndex = parentIndex;
}
}
public TValue Dequeue()
{
var lastIndex = _data.Count - 1;
var firstItem = _data[0];
_data[0] = _data[lastIndex];
_data.RemoveAt(lastIndex--);
var parentIndex = 0;
while (true)
{
var childIndex = parentIndex * 2 + 1;
if (childIndex > lastIndex)
break;
var rightChild = childIndex + 1;
if (rightChild <= lastIndex && Compare(_data[rightChild].Key, _data[childIndex].Key) < 0)
childIndex = rightChild;
if (Compare(_data[parentIndex].Key, _data[childIndex].Key) <= 0)
break;
Swap(parentIndex, childIndex);
parentIndex = childIndex;
}
return firstItem.Value;
}
public TValue Peek()
{
return _data[0].Value;
}
private void Swap(int a, int b)
{
var tmp = _data[a];
_data[a] = _data[b];
_data[b] = tmp;
}
private int Compare(TKey a, TKey b)
{
return _isDescending ? _keyComparer.Compare(b, a) : _keyComparer.Compare(a, b);
}
public int Count => _data.Count;
public IEnumerator<TValue> GetEnumerator()
{
return _data.Select(r => r.Value).GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
#endregion
#region 特殊系
/// <summary>
/// mod p の世界
/// </summary>
public class Mint
{
public long x;
public Mint(long x = 0)
{
this.x = ((x % INF + INF) % INF);
}
public static Mint operator -(Mint m, Mint n)
{
return new Mint((m.x + INF - n.x) % INF);
}
public static Mint operator -(Mint m, long n)
{
return new Mint((m.x + INF - (n % INF)) % INF);
}
public static Mint operator -(long m, Mint n)
{
return new Mint(((m % INF) + INF - n.x) % INF);
}
public static Mint operator +(Mint m, Mint n)
{
return new Mint((m.x + n.x) % INF);
}
public static Mint operator +(Mint m, long n)
{
return new Mint((m.x + (n % INF)) % INF);
}
public static Mint operator +(long m, Mint n)
{
return new Mint(((m % INF) + n.x) % INF);
}
public static Mint operator *(Mint m, Mint n)
{
return new Mint((m.x * n.x) % INF);
}
public static Mint operator *(Mint m, long n)
{
return new Mint((m.x * (n % INF)) % INF);
}
public static Mint operator *(long m, Mint n)
{
return new Mint(((m % INF) * n.x) % INF);
}
public static Mint operator /(Mint m, Mint n)
{
return new Mint((m.x * Inverse(n.x)) % INF);
}
public static Mint operator /(Mint m, long n)
{
return new Mint((m.x * Inverse((n % INF))) % INF);
}
public static Mint operator /(long m, Mint n)
{
return new Mint(((m % INF) * Inverse(n.x)) % INF);
}
}
#endregion
#endregion
}
}