結果
問題 | No.2897 2集合間距離 |
ユーザー | tobisatis |
提出日時 | 2024-09-20 23:12:04 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 1,678 ms / 3,500 ms |
コード長 | 6,008 bytes |
コンパイル時間 | 9,021 ms |
コンパイル使用メモリ | 166,400 KB |
実行使用メモリ | 316,212 KB |
最終ジャッジ日時 | 2024-09-20 23:12:29 |
合計ジャッジ時間 | 21,944 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 63 ms
31,104 KB |
testcase_01 | AC | 74 ms
31,104 KB |
testcase_02 | AC | 68 ms
30,848 KB |
testcase_03 | AC | 66 ms
31,232 KB |
testcase_04 | AC | 62 ms
31,208 KB |
testcase_05 | AC | 62 ms
30,848 KB |
testcase_06 | AC | 62 ms
30,976 KB |
testcase_07 | AC | 63 ms
31,104 KB |
testcase_08 | AC | 63 ms
30,976 KB |
testcase_09 | AC | 64 ms
31,104 KB |
testcase_10 | AC | 70 ms
31,104 KB |
testcase_11 | AC | 64 ms
31,232 KB |
testcase_12 | AC | 66 ms
31,232 KB |
testcase_13 | AC | 70 ms
32,484 KB |
testcase_14 | AC | 94 ms
34,552 KB |
testcase_15 | AC | 127 ms
40,576 KB |
testcase_16 | AC | 1,154 ms
152,144 KB |
testcase_17 | AC | 1,194 ms
152,044 KB |
testcase_18 | AC | 1,187 ms
152,264 KB |
testcase_19 | AC | 1,174 ms
151,888 KB |
testcase_20 | AC | 1,121 ms
151,876 KB |
testcase_21 | AC | 1,415 ms
151,884 KB |
testcase_22 | AC | 1,615 ms
151,888 KB |
testcase_23 | AC | 1,678 ms
316,212 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (86 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/
ソースコード
namespace AtCoder; #nullable enable using System.Numerics; class WaveletMatrix<T> where T : IAdditionOperators<T, T, T>, ISubtractionOperators<T, T, T>, IAdditiveIdentity<T, T> { const int d = 32; uint[,] Rank0 { get; init; } T[,] Sum { get; init; } int Length => Rank0.GetLength(1) - 1; public WaveletMatrix((uint, T)[] array) { var n = array.Length; var ranks = new uint[d, n + 1]; var sum = new T[d, n + 1]; var a = array.AsSpan(); var b = new (uint, T)[n].AsSpan(); var a0 = new (uint, T)[n].AsSpan(); var a1 = new (uint, T)[n].AsSpan(); for (var i = d - 1; i >= 0; i--) { var (i0, i1) = (0, 0); for (var j = 0; j < n; j++) { ranks[i, j + 1] += ranks[i, j]; var v = a[j]; if ((v.Item1 & (1U << i)) > 0) { ranks[i, j + 1]++; a1[i1++] = v; } else a0[i0++] = v; } for (var j = 0; j < i0; j++) b[j] = a0[j]; for (var j = 0; j < i1; j++) b[j + i0] = a1[j]; sum[i, 0] = T.AdditiveIdentity; for (var j = 0; j < n; j++) sum[i, j + 1] = sum[i, j] + b[j].Item2; var tmp = a; a = b; b = tmp; } for (var i = 0; i < d; i++) for (var j = 1U; j <= n; j++) ranks[i, j] = j - ranks[i, j]; (Rank0, Sum) = (ranks, sum); } public T Frequency(uint l, uint r, uint upper) // [l, r), [0, upper) { var (n, rank0, sum) = (Length, Rank0, Sum); var res = T.AdditiveIdentity; for (var i = d - 1; i >= 0; i--) { if (l >= r) break; var (l0, r0) = (rank0[i, l], rank0[i, r]); if ((upper & (1U << i)) > 0) { res += sum[i, r0] - sum[i, l0]; var zeros = rank0[i, n]; l += zeros - l0; r += zeros - r0; } else (l, r) = (l0, r0); } return res; } } class PointMap { readonly WaveletMatrix<long> matrix; readonly uint[] xs; public PointMap((uint, uint, long)[] points) { var sorted = points.OrderBy(e => e.Item1); var xs = sorted.Select(e => e.Item1); var ys = sorted.Select(e => (e.Item2, e.Item3)); matrix = new WaveletMatrix<long>(ys.ToArray()); this.xs = xs.ToArray(); } public long Sum((uint, uint) lowerLeft, (uint, uint) upperRight) // [lx, rx), [ly, ry) { var (lx, ly) = lowerLeft; var (rx, ry) = upperRight; if (lx > rx || ly > ry) return 0; return Sum(lx, ly, rx - lx, ry - ly); } public long Sum(uint x, uint y, uint dx, uint dy) // [x, x + dx), [y, y + dy) { var ux = uint.MaxValue; if (x <= ux - dx) ux = x + dx; var uy = uint.MaxValue; if (y <= uy - dy) uy = y + dy; var l = MinIndex(x); var r = MinIndex(ux); return matrix.Frequency(l, r, uy) - matrix.Frequency(l, r, y); } uint MinIndex(uint x) { var xs = this.xs; var (l, r) = (-1, xs.Length); while (r - l > 1) { var m = (l + r) >> 1; if (xs[m] < x) l = m; else r = m; } return (uint)r; } } static class Extensions { public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray(); } class AtCoder { object? Solve() { var shift = 1000; var n = Int(); var pz = new (uint, uint)[n]; for (var i = 0; i < n; i++) { var x = Int(); var y = Int(); pz[i] = ((uint)(x + y + shift), (uint)(x - y + shift)); } PointMap map; { var m = Int(); var qz = new (uint, uint, long)[m]; for (var i = 0; i < m; i++) { var x = Int(); var y = Int(); qz[i] = ((uint)(x + y + shift), (uint)(x - y + shift), 1); } map = new(qz); } bool F(uint d) { foreach (var (x, y) in pz) { var lx = 0U; if (x >= d) lx = x - d; var ly = 0U; if (y >= d) ly = y - d; var rx = x + d + 1; var ry = y + d + 1; var c = map.Sum((lx, ly), (rx, ry)); if (c > 0) return true; } return false; } if (F(0)) return 0; var fail = 0U; var pass = uint.MaxValue / 2; while (pass - fail > 1) { var middle = (pass + fail) >> 1; if (F(middle)) pass = middle; else fail = middle; } return pass; } public static void Main() => new AtCoder().Run(); public void Run() { var res = Solve(); if (res != null) { if (res is bool yes) res = yes ? "Yes" : "No"; sw.WriteLine(res); } sw.Flush(); } string[] input = Array.Empty<string>(); int iter = 0; readonly StreamWriter sw = new(Console.OpenStandardOutput()) { AutoFlush = false }; string String() { while (iter >= input.Length) (input, iter) = (Console.ReadLine()!.Split(' '), 0); return input[iter++]; } T Input<T>() where T : IParsable<T> => T.Parse(String(), null); int Int() => Input<int>(); void Out(object? x, string? separator = null) { separator ??= Environment.NewLine; if (x is System.Collections.IEnumerable obj and not string) { var firstLine = true; foreach (var item in obj) { if (!firstLine) sw.Write(separator); firstLine = false; sw.Write(item); } } else sw.Write(x); sw.WriteLine(); } }