結果
問題 | No.1332 Range Nearest Query |
ユーザー |
|
提出日時 | 2024-08-29 23:40:51 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 1,497 ms / 2,500 ms |
コード長 | 6,584 bytes |
コンパイル時間 | 14,769 ms |
コンパイル使用メモリ | 169,408 KB |
実行使用メモリ | 256,656 KB |
最終ジャッジ日時 | 2024-08-29 23:42:55 |
合計ジャッジ時間 | 71,121 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (217 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 static System.Console;using System.Linq;using System.Collections.Generic;class Program{static int NN => int.Parse(ReadLine());static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();static int[][] NArr(long n) => Enumerable.Repeat(0, (int)n).Select(_ => NList).ToArray();public static void Main(){Solve();}static void Solve(){var n = NN;var x = NList;var q = NN;var map = NArr(q);var a1 = Near(n, x, map);for (var i = 0; i < n; ++i) x[i] = 1_000_000_000 - x[i];for (var i = 0; i < q; ++i) map[i][2] = 1_000_000_000 - map[i][2];var a2 = Near(n, x, map);var ans = new int[q];for (var i = 0; i < q; ++i) ans[i] = Math.Min(a1[i], a2[i]);WriteLine(string.Join("\n", ans));}static int[] Near(int n, int[] x, int[][] query){var list = x.Select((xi, id) => (xi, id)).ToList();list.Sort((l, r) =>{var d = l.xi.CompareTo(r.xi);if (d != 0) return d;return l.id.CompareTo(r.id);});var plist = new int[n];for (var i = 0; i < n; ++i) plist[list[i].id] = i;var seg = new SegmentTree<int>(n, new SegOp());var qlist = query.Select((qi, id) => (id, qi[0], qi[1], qi[2])).ToList();qlist.Sort((l, r) => r.Item2.CompareTo(l.Item2));var ans = Enumerable.Repeat(int.MaxValue, query.Length).ToArray();var count = n - 1;foreach (var que in qlist){var li = que.Item2 - 1;var ri = que.Item3 - 1;var xi = que.Item4;while (count >= li){seg[plist[count]] = count;--count;}var pos = LowerBound(0, xi, list);if (pos < n){var p2 = seg.MaxRight(pos, v => v > ri);if (p2 < n){ans[que.id] = list[p2].xi - xi;}}}return ans;}static int LowerBound(int left, int min, IList<(int xi, int id)> list){if (list[left].xi >= min) return left;var ng = left;var ok = list.Count;while (ok - ng > 1){var center = (ng + ok) / 2;if (list[center].xi < min) ng = center;else ok = center;}return ok;}struct SegOp : ISegmentTreeOperator<int>{public int Identity => int.MaxValue;public int Operate(int x, int y){return Math.Min(x, y);}}interface ISegmentTreeOperator<T>{T Identity { get; }T Operate(T x, T y);}class SegmentTree<T>{int _n;int size;int log;T[] d;ISegmentTreeOperator<T> op;void Update(int k){d[k] = op.Operate(d[2 * k], d[2 * k + 1]);}public SegmentTree(int n, ISegmentTreeOperator<T> op){this.op = op;_n = n;size = 1;while (size < n) size <<= 1;log = CountRZero(size);d = new T[2 * size];for (var i = 0; i < d.Length; ++i) d[i] = op.Identity;}public SegmentTree(T[] v, ISegmentTreeOperator<T> op){this.op = op;_n = v.Length;size = 1;while (size < v.Length) size <<= 1;log = CountRZero(size);d = new T[2 * size];for (var i = 0; i < size; ++i) d[i] = op.Identity;for (var i = 0; i < v.Length; ++i) d[size + i] = v[i];for (var i = size - 1; i >= 1; --i) Update(i);}int CountRZero(int n){var ans = 0;while (n % 2 == 0){++ans;n >>= 1;}return ans;}public T this[int p]{get { return d[p + size]; }set{p += size;d[p] = value;for (var i = 1; i <= log; ++i) Update(p >> i);}}public T Prod(int l, int r){var sml = op.Identity;var smr = op.Identity;l += size;r += size;while (l < r){if ((l & 1) != 0) sml = op.Operate(sml, d[l++]);if ((r & 1) != 0) smr = op.Operate(d[--r], smr);l >>= 1;r >>= 1;}return op.Operate(sml, smr);}T AllProd() => d[1];public int MinLeft(int r, Predicate<T> f){if (r == 0) return 0;r += size;T sm = op.Identity;do{r--;while (r > 1 && (r % 2) != 0) r >>= 1;if (!f(op.Operate(d[r], sm))){while (r < size){r = 2 * r + 1;if (f(op.Operate(d[r], sm))){sm = op.Operate(d[r], sm);r--;}}return r + 1 - size;}sm = op.Operate(d[r], sm);}while ((r & -r) != r);return 0;}public int MaxRight(int l, Predicate<T> f){if (l == _n) return _n;l += size;T sm = op.Identity;do{while (l % 2 == 0) l >>= 1;if (!f(op.Operate(sm, d[l]))){while (l < size){l = 2 * l;if (f(op.Operate(sm, d[l]))){sm = op.Operate(sm, d[l]);++l;}}return l - size;}sm = op.Operate(sm, d[l]);++l;} while ((l & -l) != l);return _n;}}}