結果
問題 | No.674 n連勤 |
ユーザー | Risen |
提出日時 | 2024-03-28 23:28:32 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 547 ms / 2,000 ms |
コード長 | 5,192 bytes |
コンパイル時間 | 12,619 ms |
コンパイル使用メモリ | 168,132 KB |
実行使用メモリ | 221,576 KB |
最終ジャッジ日時 | 2024-09-30 14:53:09 |
合計ジャッジ時間 | 16,821 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 67 ms
31,872 KB |
testcase_01 | AC | 66 ms
31,872 KB |
testcase_02 | AC | 65 ms
31,744 KB |
testcase_03 | AC | 65 ms
31,744 KB |
testcase_04 | AC | 65 ms
31,616 KB |
testcase_05 | AC | 65 ms
31,860 KB |
testcase_06 | AC | 66 ms
31,872 KB |
testcase_07 | AC | 66 ms
31,744 KB |
testcase_08 | AC | 66 ms
31,872 KB |
testcase_09 | AC | 65 ms
31,872 KB |
testcase_10 | AC | 65 ms
31,616 KB |
testcase_11 | AC | 77 ms
35,456 KB |
testcase_12 | AC | 87 ms
39,168 KB |
testcase_13 | AC | 176 ms
60,672 KB |
testcase_14 | AC | 218 ms
60,532 KB |
testcase_15 | AC | 166 ms
58,356 KB |
testcase_16 | AC | 514 ms
59,904 KB |
testcase_17 | AC | 547 ms
59,904 KB |
testcase_18 | AC | 351 ms
57,204 KB |
testcase_19 | AC | 163 ms
221,576 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (137 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 System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Numerics; public class RangeSet<T> where T : IMinMaxValue<T>, IBinaryInteger<T> { private SortedSet<Tuple<T, T>> Set; private T Inf; public Tuple<T, T> Min { private set; get; } public Tuple<T, T> Max { private set; get; } public RangeSet() { Inf = T.MaxValue / (T.One + T.One); Set = new SortedSet<Tuple<T, T>>(); Min = new Tuple<T, T>(-Inf, -Inf); Max = new Tuple<T, T>(Inf, Inf); Set.Add(Min); Set.Add(Max); } public bool Covered(T l, T r) { Debug.Assert(l <= r); return CoveredBy(l, r) != Min; } public bool Covered(T x) { return Covered(x, x); } // [l, r]がカバーされているなら,その区間を返す. されていないなら[-TINF,-TINF]を返す public Tuple<T, T> CoveredBy(T l, T r) { Debug.Assert(l <= r); var range = Set.GetViewBetween(Min, Tuple.Create(l, Inf)).Max; return range.Item1 <= l && r <= range.Item2 ? range : Min; } public Tuple<T, T> CoveredBy(T x) { return CoveredBy(x, x); } // insert[l,r], 増加量を返す public T Insert(T l, T r) { Debug.Assert(l <= r); var range = Set.GetViewBetween(Min, Tuple.Create(l, Inf)).Max; if (range.Item1 <= l && r <= range.Item2) { return T.Zero; } T sumErased = T.Zero; if (range.Item1 <= l && l <= range.Item2 + T.One) { l = range.Item1; sumErased += range.Item2 - range.Item1 + T.One; Set.Remove(range); } var view = Set.GetViewBetween(Tuple.Create(range.Item1 + T.One, Inf), Set.Max); var last = view.Min; var removes = new List<Tuple<T, T>>(); foreach (var x in view) { last = x; if (r <= x.Item2) { break; } sumErased += x.Item2 - x.Item1 + T.One; removes.Add(x); } foreach (var x in removes) { Set.Remove(x); } if (last.Item1 - T.One <= r && r <= last.Item2) { sumErased += last.Item2 - last.Item1 + T.One; r = last.Item2; Set.Remove(last); } Set.Add(Tuple.Create(l, r)); return (r - l + T.One) - sumErased; } public T Insert(T x) { return Insert(x, x); } // erase [l,r], 減少量を返す public T Erase(T l, T r) { Debug.Assert(l <= r); var range = Set.GetViewBetween(Min, Tuple.Create(l + T.One, Inf)).Max; if (range.Item1 <= l && r <= range.Item2) { // 完全に1つの区間に包含されている if (range.Item1 < l) { Set.Add(Tuple.Create(range.Item1, l - T.One)); } if (r < range.Item2) { Set.Add(Tuple.Create(r + T.One, range.Item2)); } Set.Remove(range); return r - l + T.One; } T ret = T.Zero; if (range.Item1 <= l && l <= range.Item2) { ret += range.Item2 - l + T.One; if (range.Item1 < l) { Set.Add(Tuple.Create(range.Item1, l - T.One)); } Set.Remove(range); } var view = Set.GetViewBetween(Tuple.Create(range.Item1 + T.One, Inf), Set.Max); var last = view.Min; foreach (var x in view) { last = x; if (x.Item2 > r) { break; } ret += x.Item2 - x.Item1 + T.One; Set.Remove(x); } // 右端が区間の間にあるか if (last.Item1 <= r && r <= last.Item2) { ret += r - last.Item1 + T.One; if (r < last.Item2) { Set.Add(Tuple.Create(r + T.One, last.Item2)); } Set.Remove(last); } return ret; } public T Erase(T x) { return Erase(x, x); } public int Size() { return Set.Count - 2; } public override string ToString() { return string.Join(", ", Set.Select(x => $"[{x.Item1},{x.Item2}]")); } } public static class Solution { public static void Main() { var vals = Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); var D = vals[0]; var Q = vals[1]; var set = new RangeSet<long>(); var answer = new List<long>(); long max = 0; for (int q = 0; q < Q; q++) { vals = Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); var A = vals[0]; var B = vals[1]; set.Insert(A, B); var range = set.CoveredBy(A); var len = range == set.Min ? 0 : range.Item2 - range.Item1 + 1; max = Math.Max(max, len); answer.Add(max); } Console.WriteLine(string.Join(Environment.NewLine, answer)); } }