結果

問題 No.1332 Range Nearest Query
ユーザー さかぽんさかぽん
提出日時 2021-01-15 10:08:33
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 1,110 ms / 2,500 ms
コード長 3,263 bytes
コンパイル時間 4,455 ms
コンパイル使用メモリ 105,460 KB
実行使用メモリ 63,036 KB
最終ジャッジ日時 2023-08-16 18:07:28
合計ジャッジ時間 51,672 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 66 ms
15,848 KB
testcase_01 AC 67 ms
15,852 KB
testcase_02 AC 65 ms
15,940 KB
testcase_03 AC 995 ms
60,804 KB
testcase_04 AC 998 ms
60,868 KB
testcase_05 AC 1,013 ms
60,720 KB
testcase_06 AC 950 ms
62,868 KB
testcase_07 AC 940 ms
62,968 KB
testcase_08 AC 929 ms
62,916 KB
testcase_09 AC 941 ms
63,016 KB
testcase_10 AC 932 ms
62,916 KB
testcase_11 AC 930 ms
62,968 KB
testcase_12 AC 990 ms
62,960 KB
testcase_13 AC 931 ms
62,976 KB
testcase_14 AC 922 ms
62,952 KB
testcase_15 AC 1,053 ms
62,920 KB
testcase_16 AC 1,104 ms
62,968 KB
testcase_17 AC 1,091 ms
62,836 KB
testcase_18 AC 1,110 ms
63,004 KB
testcase_19 AC 1,093 ms
62,968 KB
testcase_20 AC 1,091 ms
62,916 KB
testcase_21 AC 1,101 ms
62,996 KB
testcase_22 AC 1,108 ms
62,892 KB
testcase_23 AC 1,103 ms
62,968 KB
testcase_24 AC 1,098 ms
62,992 KB
testcase_25 AC 1,098 ms
62,852 KB
testcase_26 AC 926 ms
62,908 KB
testcase_27 AC 883 ms
63,036 KB
testcase_28 AC 323 ms
30,568 KB
testcase_29 AC 325 ms
30,516 KB
testcase_30 AC 321 ms
30,476 KB
testcase_31 AC 322 ms
30,648 KB
testcase_32 AC 326 ms
30,488 KB
testcase_33 AC 325 ms
30,408 KB
testcase_34 AC 321 ms
30,652 KB
testcase_35 AC 322 ms
30,668 KB
testcase_36 AC 338 ms
30,600 KB
testcase_37 AC 324 ms
30,464 KB
testcase_38 AC 719 ms
48,408 KB
testcase_39 AC 379 ms
34,756 KB
testcase_40 AC 1,081 ms
62,176 KB
testcase_41 AC 495 ms
39,212 KB
testcase_42 AC 701 ms
48,016 KB
testcase_43 AC 571 ms
41,492 KB
testcase_44 AC 890 ms
56,240 KB
testcase_45 AC 832 ms
52,260 KB
testcase_46 AC 670 ms
43,260 KB
testcase_47 AC 781 ms
50,328 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Linq;

class D
{
	static int[] Read() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
	static (int x, int l, int r, int i) Read3(int i) { var a = Read(); return (a[2], a[0], a[1], i); }
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var xs = Read();
		var qc = int.Parse(Console.ReadLine());
		var qs = Enumerable.Range(0, qc).Select(Read3).ToArray();

		var mins = Array.ConvertAll(new bool[qc], _ => int.MaxValue);
		var st1 = new ST1<int>(n, Math.Max, int.MinValue);
		var st2 = new ST1<int>(n, Math.Min, int.MaxValue);

		var xqs = xs.Select((x, i) => (x, l: int.MinValue, r: 0, i)).Concat(qs).ToArray();
		// x - x_i >= 0
		var q1 = xqs.OrderBy(v => v);
		// x_i - x >= 0
		var q2 = xqs.OrderBy(v => -v.x).ThenBy(v => v.l);

		foreach (var (x, l, r, i) in q1)
			if (r == 0)
				st1.Set(i, x);
			else
			{
				var max = st1.Get(l - 1, r);
				if (max == st1.v0) continue;
				mins[i] = Math.Min(mins[i], x - max);
			}

		foreach (var (x, l, r, i) in q2)
			if (r == 0)
				st2.Set(i, x);
			else
			{
				var min = st2.Get(l - 1, r);
				if (min == st2.v0) continue;
				mins[i] = Math.Min(mins[i], min - x);
			}

		Console.WriteLine(string.Join("\n", mins));
	}
}

class ST1<TV>
{
	public struct STNode
	{
		public int i;
		public static implicit operator STNode(int i) => new STNode { i = i };
		public override string ToString() => $"{i}";

		public STNode Parent => i >> 1;
		public STNode Child0 => i << 1;
		public STNode Child1 => (i << 1) + 1;
		public STNode LastLeft(int length) => i * length;
		public STNode LastRight(int length) => (i + 1) * length;
	}

	// Power of 2
	public int n2 = 1;
	public TV[] a2;

	public Func<TV, TV, TV> Union;
	public TV v0;

	// 全ノードを、零元を表す値で初期化します (零元の Union もまた零元)。
	public ST1(int n, Func<TV, TV, TV> union, TV _v0, TV[] a0 = null)
	{
		while (n2 < n << 1) n2 <<= 1;
		a2 = new TV[n2];

		Union = union;
		v0 = _v0;
		if (!Equals(v0, default(TV)) || a0 != null) Init(a0);
	}

	public void Init(TV[] a0 = null)
	{
		if (a0 == null)
		{
			for (int i = 1; i < n2; ++i) a2[i] = v0;
		}
		else
		{
			Array.Copy(a0, 0, a2, n2 >> 1, a0.Length);
			for (int i = (n2 >> 1) + a0.Length; i < n2; ++i) a2[i] = v0;
			for (int i = (n2 >> 1) - 1; i > 0; --i) a2[i] = Union(a2[i << 1], a2[(i << 1) + 1]);
		}
	}

	public STNode Actual(int i) => (n2 >> 1) + i;
	public int Original(STNode n) => n.i - (n2 >> 1);
	public TV this[STNode n]
	{
		get { return a2[n.i]; }
		set { a2[n.i] = value; }
	}

	// Bottom-up
	public void Set(int i, TV v)
	{
		var n = Actual(i);
		a2[n.i] = v;
		while ((n = n.Parent).i > 0) a2[n.i] = Union(a2[n.Child0.i], a2[n.Child1.i]);
	}

	public TV Get(int i) => a2[(n2 >> 1) + i];
	// 範囲の昇順
	public TV Get(int l_in, int r_ex) => Aggregate(l_in, r_ex, v0, (p, n, l) => Union(p, a2[n.i]));

	// 範囲の昇順
	// (previous, node, length) => result
	public TR Aggregate<TR>(int l_in, int r_ex, TR r0, Func<TR, STNode, int, TR> func)
	{
		int al = (n2 >> 1) + l_in, ar = (n2 >> 1) + r_ex;

		var rv = r0;
		while (al < ar)
		{
			var length = al & -al;
			while (al + length > ar) length >>= 1;
			rv = func(rv, al / length, length);
			al += length;
		}
		return rv;
	}
}
0