結果
問題 | No.3101 Range Eratosthenes Query |
ユーザー |
|
提出日時 | 2025-04-11 21:31:12 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 2,409 ms / 3,000 ms |
コード長 | 3,176 bytes |
コンパイル時間 | 9,103 ms |
コンパイル使用メモリ | 173,692 KB |
実行使用メモリ | 226,448 KB |
最終ジャッジ日時 | 2025-04-11 21:32:00 |
合計ジャッジ時間 | 42,955 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (118 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
#nullable enable using System.Numerics; void Run() { var q = Int(); var queries = new List<(int l, int r, int i)>(); var max = 0; for (var i = 0; i < q; i++) { var l = Int(); var r = Int(); queries.Add((l, r, i)); max = Math.Max(max, r); } queries.Sort(); queries.Reverse(); var t = new PointAddRangeSum<int>(max + 1); for (var i = 0; i <= max; i++) t.Add(i, 1); var ans = new int[q]; var ll = max; foreach (var (l, r, i) in queries) { while (ll >= l) { for (var j = ll * 2; j <= max; j += ll) { var v = t.Sum(j, j + 1); if (v > 0) t.Add(j, -v); } ll--; } ans[i] = t.Sum(l, r + 1); } Out(ans); } #region AtCoderIO _io_; var _backend_ = new StandardIOBackend(); _io_ = new(){ Backend = _backend_ }; Run(); _backend_.Flush(); string String() => _io_.Next(); int Int() => int.Parse(String()); void Out(object? x, string? sep = null) => _io_.Out(x, sep); class AtCoderIO { public required StandardIOBackend Backend { get; init; } Memory<string> _input = Array.Empty<string>(); int _iter = 0; public string Next() { while (_iter >= _input.Length) (_input, _iter) = (Backend.ReadLine().Split(' '), 0); return _input.Span[_iter++]; } public void Out(object? x, string? separator = null) { if (x == null) return; separator ??= Environment.NewLine; if (x is System.Collections.IEnumerable a and not string) { var objects = a.Cast<object>(); if (separator == Environment.NewLine && !objects.Any()) return; x = string.Join(separator, objects); } Backend.WriteLine(x); } } class StandardIOBackend { readonly StreamReader _sr = new(Console.OpenStandardInput()); readonly StreamWriter _sw = new(Console.OpenStandardOutput()) { AutoFlush = false }; public string ReadLine() => _sr.ReadLine()!; public void WriteLine(object? value) => _sw.WriteLine(value); public void Flush() => _sw.Flush(); } #endregion static class Extensions { public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray(); } class FenwickTree<T> where T : INumber<T> { public FenwickTree(int length) { _values = new T[length + 2]; } public void Add(int i, T value) { var values = _values.Span; while (i < values.Length) { values[i] += value; i += i & -i; } } public T Sum(int i) { var values = _values.Span; var res = T.Zero; while (i > 0) { res += values[i]; i -= i & -i; } return res; } readonly Memory<T> _values; } // [0..N) class PointAddRangeSum<T> where T : INumber<T> { public PointAddRangeSum(int length) { _data = new FenwickTree<T>(length); } public void Add(int at, T value) => _data.Add(at + 1, value); public T Sum(int l, int r) => _data.Sum(r) - _data.Sum(l); // [l, r) readonly FenwickTree<T>_data; }