結果
| 問題 | No.3463 Beltway |
| コンテスト | |
| ユーザー |
👑  b1agmpo1e
|
| 提出日時 | 2026-03-18 17:14:40 |
| 言語 | C# (.NET 10.0.102) |
| 結果 |
AC
|
| 実行時間 | 586 ms / 2,000 ms |
| コード長 | 55,729 bytes |
| 記録 | |
| コンパイル時間 | 18,365 ms |
| コンパイル使用メモリ | 174,752 KB |
| 実行使用メモリ | 277,488 KB |
| 最終ジャッジ日時 | 2026-03-18 17:15:13 |
| 合計ジャッジ時間 | 31,449 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 17 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (126 ミリ秒)。 /home/judge/data/code/Main.cs(279,23): warning CS8981: 型名 'node' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(596,29): warning CS8981: 型名 'node' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(937,20): warning CS8981: 型名 'input' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(1004,20): warning CS8981: 型名 'mod' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(1027,20): warning CS8981: 型名 'toolbox' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(65,20): warning CS0169: フィールド 'Program.mod' は使用されていません [/home/judge/data/code/main.csproj] main -> /home/judge/data/code/bin/Release/net10.0/main.dll main -> /home/judge/data/code/bin/Release/net10.0/publish/
ソースコード
using System.Runtime.CompilerServices;
using System.Numerics;
using System.Runtime.InteropServices;
using System.Net;
using System.Diagnostics.CodeAnalysis;
namespace test
{
internal class Program
{
static void Main(string[] args)
{
cin = new input();
//mod = new mod(998244353);
toolbox = new toolbox();
Priority_Queue = new Priority_Queue(true);
var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(sw);
toolbox.StartTimer();
(int, int) f(int a, int b) => (Math.Min(a, b), Math.Max(a, b));
int v = cin.intreed();
int e = cin.intreed();
int start = cin.intreed();
int end = cin.intreed();
var eage = Enumerable.Repeat(0, e).Select(_ => f(cin.intreed(), cin.intreed())).ToList();
var LowLink = new LowLink(v);
foreach (var i in eage)
{
LowLink.Connect_Graph(i.Item1, i.Item2);
}
LowLink.Build();
//まず、最短経路であり、かつ通るbrigeを最小化したい
//コストを<<18して、brigeなら+1,notなら+0した辺を考えると、いい感じになりそう
var d=new Dijkstra(v,true);
foreach(var i in eage)
{
if(LowLink.Bridges.Contains(i))
d.Connect_Graph(i.Item1,i.Item2,1*(int)1e7+1);
else
d.Connect_Graph(i.Item1,i.Item2,1*(int)1e7);
}
d.Start_Dijkstra(start);
if(d.dist[end] is long.MaxValue)
System.Console.WriteLine(-1);
else
{
//System.Console.WriteLine(d.dist[end]);
long len=d.dist[end]/(long)1e7;
long cnt=d.dist[end]%(long)1e7;
System.Console.WriteLine(len-cnt);
}
toolbox.PrintElapsedTime();
Console.Out.Flush();
}
static input cin;
static mod mod;
static toolbox toolbox;
static Priority_Queue Priority_Queue;
}
public class LowLink
{
//1indexで設計 0を使うと壊れる 単純無向グラフを考えているので、多重辺があったりすると壊れる
private List<List<int>> Graph = new List<List<int>>();
private bool interactive;
private List<int> Ord;//DFS順
private List<int> Low;//1回後退していい条件のもとで、到達可能なordのmin
private int size;
public HashSet<(int, int)> Bridges = new HashSet<(int, int)>();//橋(辺) item1は小さい item2は大きい
public HashSet<int> Articulations = new HashSet<int>();//関節点
public LowLink(int n, bool cnt = true)
{
Graph = Enumerable.Repeat(0, n + 1).Select(_ => new List<int>()).ToList();
Ord = Enumerable.Repeat(-1, n + 1).ToList();
Low = Enumerable.Repeat(-1, n + 1).ToList();
interactive = cnt;
size = n;
}
public void Connect_Graph(int i, int t)
{
//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
Graph[i].Add(t);
if (interactive)
Graph[t].Add(i);
}
public void Build(int s = -1)//引数が渡されたらその頂点の連結成分しか考えない
{
int cnt = 1;
if (s is not -1)
{
dfs(s, -1);
return;
}
for (int i = 1; i <= size; i++)
dfs(i, -1);
bool dfs(int now, int prev)
{
if (Ord[now] is not -1)
return false;
Ord[now] = Low[now] = cnt++;
bool is_articulation = false;
int child_cnt = 0;//部分木がこの頂点に何本連なってるか知りたい
foreach (var i in Graph[now])
{
if (i == prev)
continue;
if (Ord[i] is not -1)
{
Low[now] = Math.Min(Low[now], Ord[i]);//サイクルにぶつかった ord[i]というのはまさに後退辺を1回使った先である
continue;
}
child_cnt++;
dfs(i, now);
Low[now] = Math.Min(Low[now], Low[i]);
if (Ord[now] < Low[i])
Bridges.Add((Math.Min(now, i), Math.Max(now, i)));//もしサイクルがなければlow[i]はord[now]より大きくなる サイクルがないということは、この辺を爆破すると連結成分が増える
if (Ord[now] <= Low[i] && prev is not -1)
is_articulation = true;//<のときは自明なので等号が成立する場合を考える それはまさに、サイクルが存在し、かつサイクルとサイクル外をつないでいるのがnowだけという時である よって、nowを爆破するとサイクルとサイクル外の連結が壊れる 例:1-2,2-3,3-4,4-5,5-2というグラフを考える この時1から探索するとord[2]とlow[5]は同じになる そして、まさに2を爆破すると、連結は{1},{3,4,5}の2つに分かれる
}
if (prev is -1 && child_cnt >= 2)
is_articulation = true;
if (is_articulation)
Articulations.Add(now);
return true;
}
}
}
internal class Dijkstra
{
static Priority_Queue Priority_Queue;
public long[] dist { get; set; }
public bool interactive { get; set; }
public int[] prev { get; set; }
/// <summary>
/// 行先,コスト
/// </summary>
public List<List<(long, long)>> Graph { get; set; }
public Dijkstra(int n, bool cnt = true)
{
Priority_Queue = new Priority_Queue(false);
dist = Enumerable.Repeat<long>(long.MaxValue, n + 1).ToArray();
Graph = new List<List<(long, long)>>();
prev = Enumerable.Repeat<int>(-1, n + 1).ToArray();//前の頂点を保管する
for (int i = 0; i <= n; i++)
{
Graph.Add(new List<(long, long)>());
}
interactive = cnt;
}
public void Connect_Graph(int i, int t, long cost)
{
//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
Graph[i].Add((t, cost));
if (interactive)
Graph[t].Add((i, cost));
}
public void Start_Dijkstra(long i)
{
dist[i] = 0;
Priority_Queue.Enqueue(0, i);
while (Priority_Queue.Queue.Count != 0)
{
var t = Priority_Queue.Dequeue();
int v = (int)t.Item2;
if (dist[v] < t.Item1)
continue;
for (int w = 0; w < Graph[v].Count; w++)
{
var e = Graph[v][w];
if (dist[(int)e.Item1] <= dist[v] + e.Item2)
continue;
else
{
dist[(int)e.Item1] = dist[v] + e.Item2;
Priority_Queue.Enqueue(dist[(int)e.Item1], e.Item1);
prev[e.Item1] = v;
}
}
}
}
public List<(int, int)> Get_tree()
{
var back = new List<(int, int)>();
for (int i = 1; i <= dist.Length - 1; i++)
{
back.Add((i, prev[i]));
}
return back;
}
}
internal class SPFA
{
private Queue<long> que;
public long[] dist { get; set; }
public bool interactive { get; set; }
public List<List<(int next, long cost)>> Graph { get; set; }
public List<long> len { get; set; }//始点からその頂点までの現在見つかっている最短経路の辺数を数える もし負閉路が存在しないなら、これは全頂点数を超えない
public List<bool> pending { get; set; }
public SPFA(int n, bool cnt = true)
{
que = new Queue<long>();
dist = Enumerable.Repeat<long>(long.MaxValue, n + 1).ToArray();
len = Enumerable.Repeat<long>(0, n + 1).ToList();
pending = Enumerable.Repeat<bool>(false, n + 1).ToList();
Graph = new List<List<(int, long)>>();
for (int i = 0; i <= n; i++)
{
Graph.Add(new List<(int, long)>());
}
interactive = cnt;
}
public void Connect_Graph(int i, int t, long cost)
{
//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
Graph[i].Add((t, cost));
if (interactive)
Graph[t].Add((i, cost));
}
public bool Start_SPFA(int i)
{
//(捜索を始める頂点(int))
que.Enqueue(i);
pending[i] = true;
dist[i] = 0;
len[i] = 0;
while (que.Count != 0)
{
var t = (int)que.Dequeue();
pending[t] = false;
for (int w = 0; w < Graph[t].Count; w++)
{
long cost_before = dist[t] + Graph[t][w].Item2;
if (dist[Graph[t][w].Item1] <= cost_before)
continue;
dist[Graph[t][w].Item1] = cost_before;
if ((len[Graph[t][w].Item1] = len[t] + 1) >= Graph.Count - 1)//1indexなので1つズレてる 超頂点とか倍化すると検出が遅れるが、検出自体は壊れないはず
return false;//負閉路
if (!pending[(int)Graph[t][w].Item1])
{
que.Enqueue(Graph[t][w].Item1);
pending[(int)Graph[t][w].Item1] = true;
}
}
}
return true;//負閉路はない
}
}
public class Treap
{
//1-indexです!!!!!!
private class node
{
public long val;
public node left;//小さい
public node right;//大きい
public int cnt;//部分木の大きさ
public int priority;//優先度
public node(long val, int priority, node left = null, node right = null)
{
this.val = val;
this.priority = priority;
this.left = left;
this.right = right;
}
public long update()
{
cnt = 1;
if (left != null) cnt += left.cnt;
if (right != null) cnt += right.cnt;
return cnt;
}
}
private node root;
private Random rand;
public Treap(int seed = 998244353)
{
root = null;
rand = new Random(seed);
}
//内部向け
//key未満のノードとkey以上のノードに分割する
private void Split(node t, long key, out node left, out node right)
{
if (t == null)
{
left = null;
right = null;
return;
}
else if (key <= t.val)
{
//key以上なので、今回のノードと右側部分木は右に行く
Split(t.left, key, out left, out t.left);
right = t;
}
else
{
//key未満なので、今回のノードと右側部分木は右に行く
Split(t.right, key, out t.right, out right);
left = t;
}
t.update();
}
//左と右を合体した新たな木(t)を作る
private void Marge(ref node t, node left, node right)
{
if (left == null || right == null)
{
t = left ?? right;
}
else if (left.priority > right.priority)
{
//leftの方が優先度高い
Marge(ref left.right, left.right, right);
t = left;
}
else
{
//rightの方が優先度高い
Marge(ref right.left, left, right.left);
t = right;
}
if (t != null) t.update();
}
private void Insert(ref node t, node item)
{
if (t == null)
{
t = item;
}
else if (item.priority > t.priority)
{
//itemの方が優先度高い このノードをitemに置き換える 今のノードtはledtかrightに入る
Split(t, item.val, out item.left, out item.right);
t = item;
}
else
{
//こいつは優先度がヒープになることに反するので、下に潜る
Insert(ref item.val < t.val ? ref t.left : ref t.right, item);
}
t.update();
}
private void Erase(ref node t, long key)
{
if (t == null) return;
if (t.val == key)
{
//今いるノードを消す このノードを子供をマージしてできた木に置き換える
Marge(ref t, t.left, t.right);
}
else
{
//このノードは消したいノードじゃない
Erase(ref key < t.val ? ref t.left : ref t.right, key);
}
if (t != null) t.update();
}
private bool Find(node t, long key)
{
if (t == null) return false;
if (t.val == key) return true;
return Find(key < t.val ? t.left : t.right, key);
}
private long GetKth(node t, int k)
{
if (t == null || k < 1 || k > t.cnt)
throw new ArgumentOutOfRangeException(nameof(k));
int leftCount = t.left != null ? t.left.cnt : 0;
if (k <= leftCount)
{
return GetKth(t.left, k);
}
else if (k == leftCount + 1)
{
return t.val;
}
else
{
return GetKth(t.right, k - leftCount - 1);
}
}
//left以上 right未満の世界でk番目に小さい要素を取得する
private long GetKth(long l, long r, int k)
{
// Split は「< key / >= key」
Split(root, l, out node LessThanLeft, out node LeftOrMore); // (<l) と (>=l)
Split(LeftOrMore, r, out node inLR, out node MoreThanR); // ([l,r)) と (>=r)
if (inLR == null || k < 1 || k > inLR.cnt)
throw new ArgumentOutOfRangeException(nameof(k));
var nd = GetKth(inLR, k);
// 必ず元に戻す（例外時も含めて復元）
node back = null;
Marge(ref back, inLR, MoreThanR); // back = (>=l) を復元
Marge(ref root, LessThanLeft, back); // root を復元
return nd;
}
private long FastGetKth(long l, long r, int k) => GetKth(root, CountLower(l) + k);
// 要素 < val の個数を数える（非再帰・O(log N)）
private int CountLower(long val)
{
int cnt = 0;
var t = root;
while (t != null)
{
if (t.val < val)
{
cnt += (t.left?.cnt ?? 0) + 1;
t = t.right;
}
else
{
t = t.left;
}
}
return cnt;
}
// k(1-indexed) 番目のノードを返すワーカー。見つからなければ null
private node GetNode(node t, int k)
{
while (t != null)
{
int lc = t.left?.cnt ?? 0;
if (k <= lc)
{
t = t.left;
}
else if (k == lc + 1)
{
return t;
}
else
{
k -= lc + 1;
t = t.right;
}
}
return null;
}
// val 以上の最初の要素のインデックス（1-indexed）。なければ Count()+1
private int LowerBoundIndex(long val) => CountLower(val) + 1;
// val より大きい最初の要素のインデックス（1-indexed）。なければ Count()+1
private int UpperBoundIndex(long val) => CountLower(checked(val + 1)) + 1;
// ノード版：見つからなければ null
private node LowerBoundNode(long val)
{
int idx = LowerBoundIndex(val);
return (idx <= Count()) ? GetNode(root, idx) : null;
}
private node UpperBoundNode(long val)
{
int idx = UpperBoundIndex(val);
return (idx <= Count()) ? GetNode(root, idx) : null;
}
//外部向け
public void Insert(long key) => Insert(ref root, new node(key, rand.Next()));
public void Erase(long key) => Erase(ref root, key);
public bool Find(long key) => Find(root, key);
public int Count() => root?.cnt ?? 0;
public long this[int index] => GetKth(root, index);
//public long GetKth(long l, long r, int k) => this.GetKth(l, r, k); 名前ぶつかっちゃった 悲しいね
public long this[long l, long r, int k] => FastGetKth(l, r, k);
public void test()
{
for (int i = 1; i <= 10; i++)
{
Insert(i);
}
Split(root, 5, out var left, out var right);
for (int i = 1; i <= 5; i++)
{
System.Console.WriteLine($"{i},==>{Find(left, i)}");
}
System.Console.WriteLine("---");
for (int i = 5; i <= 10; i++)
{
System.Console.WriteLine($"{i},==>{Find(right, i)}");
}
System.Console.WriteLine("===");
Marge(ref root, left, right);
for (int i = 1; i <= 10; i++)
{
System.Console.WriteLine($"{i},==>{Find(root, i)}");
}
}
}
public class ThisIsNotAWavelet_Matrix<T1>
where T1 : struct, IComparable
{
//1index!!
//クエリの失敗は-1またはstatus==false
public class Compress<T2>
where T2 : struct, IComparable
{
//1indexだよ!!!! 例[1,5,8,9,5,5]=>[1,2,3,4,2,2]
public Dictionary<int, T2> key2raw;
public Dictionary<T2, int> raw2key;
//やりたいこと 構築 生=>圧縮後 圧縮後=>生
public Compress(IEnumerable<T2> vector = null)
{
key2raw = new Dictionary<int, T2>();
raw2key = new Dictionary<T2, int>();
if (vector is { })
Build(vector);
}
public (List<int>, IOrderedEnumerable<T2>) Build(IEnumerable<T2> vector)
{
int cnt = 0;
var back = new List<int>();
var sorted = vector.OrderBy(i => i);
foreach (var i in sorted)
{
if (!raw2key.ContainsKey(i))
{
cnt++;
raw2key.Add(i, cnt);
key2raw.Add(cnt, i);
}
}
foreach (var i in vector)
back.Add(raw2key[i]);
return (back, sorted);
}
//インデクサは圧縮後=>生
public T2 this[int k] => key2raw[k];
public int Count => key2raw.Count;
}
public class SegmentTree
{
//たまには1indexで書いてみたくないですか？ 書きたい
//とりあえずrange sum
internal struct node
{
//index=0のnodeはnullを表す
public int val;
public int left;
public int right;
public node(int a) => val = a;
public node()
{
val = 0;
left = 0;
right = 0;
}
}
public List<int> roots;//roots[i]=>バージョンiのrootのインデックス root[0]は0が入っている
internal node[] nodes;
internal int size;
private int now_index;
//5*1e5回のsetをすると、nodesizeは2*1e7でギリギリ(400MB程度) 5*1e7でも速度的には大丈夫だけど、メモリがやばい(900MBギリ下回るぐらい)
public SegmentTree(int n, int nodesize = 5 * (int)1e7)
{
size = 1;
while (size < n) size <<= 1;
nodes = Enumerable.Repeat(new node(), nodesize).ToArray();
now_index = 2;
roots = [0, 1];
}
public int add(int val, int index, int version = 1)
{
int root = add(val, index, roots[version], 1, size + 1);
if (root == -1) return -1;
roots.Add(root);
return roots.Count - 1;
}
/// <summary>
///
/// </summary>
/// <param name="val">代入する値</param>
/// <param name="index">代入する位置(1index)</param>
/// <param name="node_index">現在のノード</param>
/// <param name="l">現在のノードが担当する範囲の左側(閉区間)</param>
/// <param name="r">右側(開区間)</param>
/// <returns>更新後の木のversion</returns>
private int add(int val, int index, int node_index, int l, int r)
{
if (index < l || r <= index) return -1;
int now = newnode();
nodes[now] = nodes[node_index];
if (l + 1 == r)
{
nodes[now].val += val;
return now;
}
int mid = (l + r) >> 1;
if (index < mid)
{
int left = add(val, index, nodes[node_index].left, l, mid);
if (left == -1) return -1;
nodes[now].left = left;
}
else
{
int right = add(val, index, nodes[node_index].right, mid, r);
if (right == -1) return -1;
nodes[now].right = right;
}
nodes[now].val = nodes[nodes[now].left].val + nodes[nodes[now].right].val;
return now;
}
/// <summary>
/// [l,r)
/// </summary>
/// <param name="l"></param>
/// <param name="r"></param>
/// <param name="version"></param>
/// <returns></returns>
public int query(int l, int r, int version = 1) => query(l, r, roots[version], 1, size + 1);
private int query(int a, int b, int node_index, int l, int r)
{
if (node_index == 0) return 0;//nullノード
if (b <= l || r <= a) return 0;//範囲外
if (a <= l && r <= b) return nodes[node_index].val;//完全被覆
int mid = (l + r) >> 1;
int left = query(a, b, nodes[node_index].left, l, mid);
int right = query(a, b, nodes[node_index].right, mid, r);
return left + right;
}
/// <summary>
/// 1index
/// </summary>
/// <param name="index"></param>
/// <param name="version"></param>
/// <returns></returns>
public int get(int index, int version = 1)
{
int l = 1;
int r = size + 1;
int now = roots[version];
while (true)
{
if (now == 0)
return 0;//nullノード
if (index < l || r <= index) return 0;
if (l + 1 == r)
return nodes[now].val;
int mid = (l + r) >> 1;
if (index < mid)
{
now = nodes[now].left;
r = mid;
}
else
{
now = nodes[now].right;
l = mid;
}
}
}
private int newnode() => now_index++;
}
public SegmentTree tree;
public Compress<T1> comp;
public List<T1> rows;//重複を排除した座標圧縮前の配列の要素全て(ソート済み)
private const int NodePoolMargin = 100;
public ThisIsNotAWavelet_Matrix(IEnumerable<T1> arr)
{
//座標圧縮してから構築する
comp = new Compress<T1>();
var comped = comp.Build(arr);
int nodesize = GetNodePoolSize();
tree = new SegmentTree(comp.Count + 1, nodesize);
int version = 1;
foreach (var i in comped.Item1)
{
version = tree.add(1, i, version);
}
rows = comped.Item2.Distinct().ToList();
int GetNodePoolSize()
{
int n = comped.Item1.Count;
int k = comp.Count + 1;
int size = 1;
int height = 0;
while (size < k)
{
size <<= 1;
height++;
}
height++;
return 2 + n * height + NodePoolMargin;//2(nullと初期ノード)+n*(add1回で作らないといけないノード数<=>木の高さ)+マージン
}
}
//区間[a,b)でk番目に大きい値を取得する
public (T1, bool status) GetKthLargest(int a, int b, int k)
{
//root[b]とroot[a]を見比べればいい varsion=1は全て0の状態 version=2がarrの最初の要素を入れた状態であることに注意せよ つまり、versionは1ずれている
if (a < 1 || b < 1 || a >= b) return (default, false);//区間が不正
if (b > tree.roots.Count - 1) return (default, false);//範囲外
long total = tree.nodes[tree.roots[b]].val - tree.nodes[tree.roots[a]].val;
if (k <= 0 || total < k) return (default, false);//そんな要素ないです
//今見てるノード
int node_a = tree.roots[a];
int node_b = tree.roots[b];
//今見てる区間
int l = 1;
int r = tree.size + 1;
while (l + 1 != r)
{
int left_a = tree.nodes[node_a].left;
int left_b = tree.nodes[node_b].left;
int right_a = tree.nodes[node_a].right;
int right_b = tree.nodes[node_b].right;
int cnt_right = tree.nodes[right_b].val - tree.nodes[right_a].val;//この区間の右側にある要素数
int mid = (l + r) >> 1;
if (cnt_right >= k)
{
node_a = right_a;
node_b = right_b;
l = mid;
}
else
{
k -= cnt_right;
node_a = left_a;
node_b = left_b;
r = mid;
}
}
return (comp[l], true);
}
//区間[a,b)でk番目に小さい値を返す
public (T1, bool) GetKthSmallest(int a, int b, int k)
{
if (a < 1 || b < 1 || a >= b) return (default, false);//区間が不正
if (b > tree.roots.Count - 1) return (default, false);//範囲外
int total = tree.nodes[tree.roots[b]].val - tree.nodes[tree.roots[a]].val;
if (k <= 0 || total < k) return (default, false);//そんな要素ないです
return GetKthLargest(a, b, total - k + 1);//k番目に大きい値に変更して投げる
}
//区間[a,b)の要素で[x,y)を満たすものの要素を数える a,b,x,yのどれかが不正だと壊れるよ
public int RangeFreq(int a, int b, T1 x, T1 y) => CountLower(a, b, y) - CountLower(a, b, x);
//区間[a,b)の要素でx未満の要素の数を数える
public int CountLower(int a, int b, T1 x)
{
if (a < 1 || b < 1 || a >= b) return -1;//区間が不正
if (b > tree.roots.Count - 1) return -1;//範囲外
int x_comped = rows.BinarySearch(x);
if (x_comped < 0) x_comped = ~x_comped;
x_comped++;
int l = tree.query(1, x_comped, a);//[1,a)でのクエリ結果
var r = tree.query(1, x_comped, b);//[1,b)でのクエリ結果
//xを圧縮後の世界に飛ばす x未満を数えるから、xを超える最小値を探してきて、それでいい
return r - l;//[1,b)-[1,a)=[a,b)
}
//区間[a,b)でx未満の最大値を返す
public (T1, bool status) PrevValue(int a, int b, T1 x)
{
//サボり実装
int cnt = CountLower(a, b, x);//区間[a,b)でx未満の個数を数える
if (cnt <= 0) return (default, false);
return GetKthSmallest(a, b, cnt);//求める値はcnt番目に小さいもの
}
//区間[a,b)でx以上の最小値を返す
public (T1, bool status) NextValue(int a, int b, T1 x)
{
int cnt = CountLower(a, b, x);//区間[a,b)でx未満の個数を数える
if (cnt < 0) return (default, false);
return GetKthSmallest(a, b, cnt + 1);//cnt+1はx以上になる最初の値の順位
}
//区間[1,b)でxが登場する回数を返す
public int Count(int b, T1 x)
{
var index = rows.BinarySearch(x);
if (index < 0)
return 0;//xは1度も登場しない
index++;
return tree.get(index, b);
}
//区間[a,b)でxが登場する回数を返す
public int Count(int a, int b, T1 x) => Count(b, x) - Count(a, x);
//区間[a,b)で要素xがi回目に登場するインデックスを返す 計算量O(logN*log(種類数))
public int Select(int a, int b, T1 x, int cnt)
{
//xは座標圧縮後であることに注意せよ
int Count(int a, int b, int x) => tree.get(x, b) - tree.get(x, a);
if (a < 1 || b < 1 || a >= b) return -1;//区間が不正
if (b > tree.roots.Count - 1) return -1;//範囲外
if (cnt <= 0) return -1;
var index = rows.BinarySearch(x);
if (index < 0) return -1;//そんな要素存在しない
index++;
int total = Count(a, b, index);
if (total < cnt) return -1;
int l = a;
int r = b;
while (l + 1 < r)
{
int mid = (l + r) >> 1;
int left = Count(l, mid, index);
if (left >= cnt)
{
r = mid;
}
else
{
l = mid;
cnt -= left;
}
}
return l;
}
}
public static class Extensions
{
public static Dictionary<T, int> safe_addtion_for_dictionary_int<T>(this Dictionary<T, int> dic, T key)
{
if (dic.ContainsKey(key))
dic[key]++;
else
dic.Add(key, 1);
return dic;
}
public static Dictionary<T, long> safe_addtion_for_dictionary_long<T>(this Dictionary<T, long> dic, T key)
{
if (dic.ContainsKey(key))
dic[key]++;
else
dic.Add(key, 1);
return dic;
}
public static Dictionary<T, List<T2>> safe_addtion_for_list_in_dictionary<T, T2>(this Dictionary<T, List<T2>> dic, T key, T2 value)
{
if (dic.ContainsKey(key))
dic[key].Add(value);
else
dic.Add(key, new List<T2>() { value });
return dic;
}
public static T list_pop_back<T>(this List<T> a)
{
var k = a[a.Count - 1];
a.RemoveAt(a.Count - 1);
return k;
}
public static T chmin<T>(ref this T a, T b)
where T : struct, IComparable
{
if (a.CompareTo(b) > 0)
return a = b;
else
return a;
}
public static T chmax<T>(ref this T a, T b)
where T : struct, IComparable
{
if (a.CompareTo(b) < 0)
return a = b;
else
return a;
}
}
internal class input
{
string[] soloinput;
int t;
public input()
{
soloinput = new string[0];
t = 0;
}
public string soloreed()
{
if (t < soloinput.Length)
{
return soloinput[t++];
}
string input = Console.ReadLine();
while (input == "")
{
input = Console.ReadLine();
}
soloinput = input.Split(" ");
t = 0;
return soloinput[t++];
}
public int intreed()
{
return int.Parse(soloreed());
}
public int[] arrayint(int N)
{
int[] A = new int[N];
for (int i = 0; i < N; i++)
{
A[i] = intreed();
}
return A;
}
public long longreed()
{
return long.Parse(soloreed());
}
public long[] arraylong(long N)
{
long[] A = new long[N];
for (long i = 0; i < N; i++)
{
A[i] = longreed();
}
return A;
}
public decimal decimalreed()
{
return decimal.Parse(soloreed());
}
public decimal[] arraydecimal(long N)
{
decimal[] A = new decimal[N];
for (decimal i = 0; i < N; i++)
{
A[(long)i] = decimalreed();
}
return A;
}
}
internal class mod
{
public long T { get; set; }
public mod(long mod = 1000000007)
{
T = mod;
}
public long addition(long A, long B)
{
long C = A + B;
return (long)C % T;
}
public long subtraction(long A, long B)
{
return ((A % T) - (B % T) + T) % T;
}
public long multiplication(long A, long B)
{
return ((A % T) * (B % T)) % T;
}
}
internal class toolbox
{
string Y = "Yes";
string N = "No";
static input cin;
private DateTime? startTime;
public toolbox()
{
cin = new input();
}
public long[] CumulativeSum(long[] A, bool mode = true)
{
if (mode == false) Array.Reverse(A);
long[] back = new long[A.Length + 1];
back[0] = 0;
for (int i = 1; i <= A.Length; i++)
{
back[i] = back[i - 1] + A[i - 1];
}
if (mode == false) Array.Reverse(A);
return back;
}
public long[] Eratosthenes(long A)
{
A++;
var back = new List<long>();
bool[] ch = new bool[A];
for (int i = 2; i < A; i++) ch[i] = true;
for (long i = 2; i < Math.Sqrt(A); i++)
{
if (ch[i] == true)
{
back.Add(i);
for (long t = 1; i * t < A; t++)
{
ch[i * t] = false;
}
}
}
for (long i = 0; i < A; i++)
{
if (ch[i] == true) back.Add(i);
}
return back.Distinct().ToArray();
}
public void Swap<T>(ref T a, ref T b)
{
var i = a;
a = b;
b = i;
}
public void LSwap<T>(ref List<T> A, int a, int b)
{
var i = A[a];
A[a] = A[b];
A[b] = i;
}
public long Gcd(long A, long B)
{
while (A != 0)
{
B %= A;
Swap(ref A, ref B);
}
return B;
}
public long[] AllDivisors(long N)
{
var back = new List<long>();
for (int i = 1; Math.Pow(i, 2) <= N; i++)
{
if (N % i == 0)
{
back.Add(i);
back.Add(N / i);
}
}
return back.Distinct().ToArray();
}
public static IEnumerable<T[]> ExhaustiveEnumeration<T>(IEnumerable<T> indata)
{
if (indata.Count() == 1) yield return new T[] { indata.First() };
foreach (var i in indata)
{
var used = new T[] { i };
var unused = indata.Except(used);
foreach (var t in ExhaustiveEnumeration(unused))
yield return used.Concat(t).ToArray();
}
//How to use
//var allpattern = toolbox.ExhaustiveEnumeration(Enumerable.Range(1, N));
}
public bool[,] bitallsearch(int N)
{
bool[,] back = new bool[(int)Math.Pow(2, N), N];
for (int i = 0; i < Math.Pow(2, N); i++)
{
for (int t = 0; t < N; t++)
{
var k = (i >> t) & 1;
if (k == 1)
{
back[i, t] = true;
}
}
}
return back;
}
public static int BS<T>(T[] A, T key)
where T : IComparable
{
//このコード、定数倍が大変な事になってるので標準ライブラリを使いましょう(BinarySearch)
int left = 0;
int right = A.Length;
int mid = 0;
while (left < right)
{
mid = (left + right) / 2;
if (A[mid].CompareTo(key) == 0)
return mid;
else if (A[mid].CompareTo(key) > 0)
right = mid;
else if (A[mid].CompareTo(key) < 0)
left = mid + 1;
}
return -1;
}
//単調増加なaの中で、v2"以上"の値を取る最小のインデックスを返す 存在しない場合。a.Count+1を返す
public static int lower_bound<T>(T[] a, T v)
{
return lower_bound(a, v, Comparer<T>.Default);
}
public static int lower_bound<T>(T[] A, T key, Comparer<T> v)
{
int left = 0;
int right = A.Length - 1;
int mid = 0;
var W = 0;
while (left <= right)
{
mid = (left + right) / 2;
W = v.Compare(A[mid], key);
if (W == -1)
left = mid + 1;
else
right = mid - 1;
}
return left;
}
public long[] prime_factorize(long N)
{
long T = N;
var back = new List<long>();
for (long i = 2; i * i <= T; i++)
{
if (T % i != 0) continue;
while (T % i == 0)
{
back.Add(i);
T /= i;
}
}
if (T != 1) back.Add(T);
return back.ToArray();
}
public long[] One_dimensional_Coordinate_Compression(long[] A)
{
long[] back = new long[A.Length];
var T = A.Distinct().ToList();
T.Sort();
for (int i = 0; i < A.Length; i++)
back[i] = T.BinarySearch(A[i]);
return back;
}
public void setYN(string A = "Yes", string B = "No")
{
Y = A;
N = B;
}
public void YN(bool ans)
{
if (ans)
Console.WriteLine(Y);
else
Console.WriteLine(N);
}
public string[] x_dekakou(int H, int W)
{
var s = new string[H + 2];
for (int i = 0; i < W + 2; i++)
{
s[0] += "x";
s[H + 1] += "x";
}
for (int i = 1; i < H + 1; i++)
{
//x場外 .白 #黒
s[i] = "x" + Console.ReadLine().Replace(" ", "") + "x";
}
return s;
}
public List<List<char>> x_dekakou_char(int H, int W)
{
var grid = new List<List<char>>(H + 2);
var border = new List<char>(W + 2);
for (int i = 0; i < W + 2; i++)
border.Add('x');
grid.Add(new List<char>(border));
for (int i = 0; i < H; i++)
{
var line = Console.ReadLine()?.Replace(" ", "") ?? string.Empty;
var row = new List<char>(W + 2);
row.Add('x');
foreach (var c in line)
row.Add(c);
row.Add('x');
grid.Add(row);
}
grid.Add(new List<char>(border));
return grid;
}
public List<List<int>> x_dekakou_string(int H, int W)
{
var back = new List<List<int>>();
for (int i = 0; i < H + 2; i++)
back.Add(Enumerable.Repeat<int>(-1, W + 2).ToList());
for (int i = 0; i < W + 2; i++)
{
back[0][i] = -1;
back[H + 1][i] = -1;
}
for (int i = 1; i <= H; i++)
{
back[i][0] = -1;
back[i][W + 1] = -1;
for (int t = 1; t <= W; t++)
back[i][t] = cin.intreed();
}
return back;
}
/// <summary>
/// 配列の指定位置以降を反転する
/// </summary>
/// <param name="array">反転対象の配列</param>
/// <param name="begin">反転開始位置（この位置以降が反転される）</param>
private void Reverse<T>(T[] array, int begin) where T : IComparable<T>
{
// 反転する要素が2個未満の場合は何もしない
if (array.Length - begin < 2) return;
// 両端から中央に向かって要素を交換
int left = begin;
int right = array.Length - 1;
while (left < right)
{
Swap(ref array[left], ref array[right]);
left++;
right--;
}
}
/// <summary>
/// 配列を辞書順で次の順列に変更する
/// 全ての順列を列挙するには、事前に Array.Sort() でソートした配列を渡すこと
/// </summary>
/// <param name="array">順列を生成する配列（事前ソート必須）</param>
/// <returns>次の順列が存在する場合true、最大順列の場合false</returns>
public bool NextPermutation<T>(T[] array) where T : IComparable<T>
{
// 辞書順で次に大きい順列を生成
// 1. 右端から降順でない位置を探す
int pivotIndex = -1;
for (int i = array.Length - 2; i >= 0; i--)
{
if (array[i].CompareTo(array[i + 1]) < 0) // 昇順ペア発見
{
pivotIndex = i;
break;
}
}
// 最大順列に到達している場合
if (pivotIndex == -1) return false;
// 2. pivotより大きい最右の要素と交換
for (int j = array.Length - 1; j > pivotIndex; j--)
{
if (array[pivotIndex].CompareTo(array[j]) < 0)
{
Swap(ref array[pivotIndex], ref array[j]);
break;
}
}
// 3. pivot以降を昇順に並べ直し
Reverse(array, pivotIndex + 1);
return true;
// how to use
// do{}while(NextPermutation)
}
/// <summary>
/// 回文判定のコア処理（配列版）
/// </summary>
private bool IsPalindromeCore<T>(T[] array, int left, int right) where T : IComparable<T>
{
while (left < right)
{
if (array[left].CompareTo(array[right]) != 0)
return false;
left++;
right--;
}
return true;
}
/// <summary>
/// 回文判定のコア処理（文字列版）
/// </summary>
private bool IsPalindromeCore(string str, int left, int right)
{
while (left < right)
{
if (str[left] != str[right])
return false;
left++;
right--;
}
return true;
}
/// <summary>
/// 配列全体が回文かどうかを判定
/// </summary>
public bool IsPalindrome<T>(T[] array) where T : IComparable<T>
{
return IsPalindromeCore(array, 0, array.Length - 1);
}
/// <summary>
/// 文字列全体が回文かどうかを判定
/// </summary>
public bool IsPalindrome(string str)
{
return IsPalindromeCore(str, 0, str.Length - 1);
}
/// <summary>
/// 指定範囲が回文かどうかを判定（配列版）
/// </summary>
public bool IsPalindrome<T>(T[] array, int start, int end) where T : IComparable<T>
{
return IsPalindromeCore(array, start, end);
}
/// <summary>
/// 指定範囲が回文かどうかを判定（文字列版）
/// </summary>
public bool IsPalindrome(string str, int start, int end)
{
return IsPalindromeCore(str, start, end);
}
/// <summary>
/// 指定長さの部分配列に回文が含まれるかを判定
/// </summary>
public bool HasPalindrome<T>(T[] array, int length) where T : IComparable<T>
{
for (int i = 0; i <= array.Length - length; i++)
{
if (IsPalindromeCore(array, i, i + length - 1))
return true;
}
return false;
}
/// <summary>
/// 指定長さの部分文字列に回文が含まれるかを判定
/// </summary>
public bool HasPalindrome(string str, int length)
{
for (int i = 0; i <= str.Length - length; i++)
{
if (IsPalindromeCore(str, i, i + length - 1))
return true;
}
return false;
}
public long modpow(long x, long p, long mod = 1000000007)
{
long result = 1;
x %= mod;
while (p > 0)
{
if (p % 2 == 1) // pが奇数の場合
{
result = (result * x) % mod;
}
x = (x * x) % mod; // xを二乗（これが繰り返し二乗）
p /= 2; // pを半分にする
}
return result;
}
public void StartTimer()
{
startTime = DateTime.Now;
}
public void PrintElapsedTime(bool error_output = true)
{
//標準出力ではなくて標準エラー出力を使ってるのでatcoderのジャッジはこの出力を無視する つまり消さなくてok 便利だね
if (startTime.HasValue)
{
var elapsed = DateTime.Now - startTime.Value;
if (error_output)
Console.Error.WriteLine($"Elapsed time: {elapsed.TotalMilliseconds} ms");
else
Console.WriteLine($"Elapsed time: {elapsed.TotalMilliseconds} ms");
}
else
{
Console.Error.WriteLine("Timer was not started.");
}
}
}
internal class Priority_Queue
{
toolbox toolbox = new toolbox();
public List<(long, long)> Queue { get; private set; }
/// <summary>
/// true==>大きいやつから出るよ false==>小さいやつからでるよ
/// </summary>
public bool revase { get; set; }
public Priority_Queue(bool cnt = true)
{
Queue = new List<(long, long)>();
revase = cnt;
}
/// <summary>
/// ヒープをO(N)で初期化するテク
/// </summary>
/// <param name="arr"></param>
/// <param name="cnt"></param>
public Priority_Queue(IEnumerable<(long, long)> arr, bool cnt = true)
{
revase = cnt;
Queue = new List<(long, long)>();
foreach (var item in arr)
{
var a = item.Item1;
if (revase == false)
a *= -1;
Queue.Add((a, item.Item2));
}
for (int i = Queue.Count / 2 - 1; i >= 0; i--)
{
int idx = i;
while (true)
{
int left = idx * 2 + 1;
if (left >= Queue.Count)
break;
int right = left + 1;
int child = left;
if (right < Queue.Count && Queue[left].Item1 < Queue[right].Item1)
child = right;
if (Queue[idx].Item1 < Queue[child].Item1)
{
var k = Queue[idx];
Queue[idx] = Queue[child];
Queue[child] = k;
idx = child;
}
else
{
break;
}
}
}
}
public void Enqueue(long a, long b)
{
if (revase == false)
a *= -1;
int i = Queue.Count, t;
Queue.Add((a, b));
while (i != 0)
{
t = (i - 1) / 2;
if (Queue[i].Item1 > Queue[t].Item1)
{
var k = Queue[i];
Queue[i] = Queue[t];
Queue[t] = k;
i = t;
}
else
{
break;
}
}
}
public (long, long) Dequeue()
{
int a = Queue.Count - 1;
var back = Queue[0];
Queue[0] = Queue[a];
Queue.RemoveAt(a);
for (int i = 0, j; (j = 2 * i + 1) < a;)
{
if (j != a - 1 && Queue[j].Item1 < Queue[j + 1].Item1)
j++;
if (Queue[i].Item1 < Queue[j].Item1)
{
var k = Queue[i];
Queue[i] = Queue[j];
Queue[j] = k;
i = j;
}
else
{
break;
}
}
if (revase == false)
back.Item1 *= -1;
return back;
}
public (long, long) GetPeek() => (revase ? Queue[0].Item1 : Queue[0].Item1 * -1, Queue[0].Item2);
}
internal class Generic_Priority_Queue<T>
{
toolbox toolbox = new toolbox();
public List<(long, T)> Queue { get; private set; }
/// <summary>
/// true==>大きいやつから出るよ false==>小さいやつからでるよ
/// </summary>
public bool revase { get; set; }
public Generic_Priority_Queue(bool cnt = true)
{
Queue = new List<(long, T)>();
revase = cnt;
}
public void Enqueue(long a, T b)
{
if (revase == false)
a *= -1;
int i = Queue.Count, t;
Queue.Add((a, b));
while (i != 0)
{
t = (i - 1) / 2;
if (Queue[i].Item1 > Queue[t].Item1)
{
var k = Queue[i];
Queue[i] = Queue[t];
Queue[t] = k;
i = t;
}
else
{
break;
}
}
}
public (long, T) Dequeue()
{
int a = Queue.Count - 1;
var back = Queue[0];
Queue[0] = Queue[a];
Queue.RemoveAt(a);
for (int i = 0, j; (j = 2 * i + 1) < a;)
{
if (j != a - 1 && Queue[j].Item1 < Queue[j + 1].Item1)
j++;
if (Queue[i].Item1 < Queue[j].Item1)
{
var k = Queue[i];
Queue[i] = Queue[j];
Queue[j] = k;
i = j;
}
else
{
break;
}
}
if (revase == false)
back.Item1 *= -1;
return back;
}
public (long, T) get_first()
{
if (Queue.Count == 0)
return (default(long), default(T));
else
return Queue[0];
}
}
}