#965304 (C#) No.674 n連勤

• 問題: No.674 n連勤
• ユーザー: Risen
• 提出日時: 2024-03-28 23:28:32
• 言語: C# (.NET 8.0.203)
• 結果: AC
• 実行時間: 656 ms / 2,000 ms
• コード長: 5,192 bytes
• コンパイル時間: 11,569 ms
• コンパイル使用メモリ: 159,032 KB
• 実行使用メモリ: 211,380 KB
• 最終ジャッジ日時: 2024-03-28 23:28:53
• 合計ジャッジ時間: 17,348 ms
• ジャッジサーバーID （参考情報）: judge15 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	88 ms; 34,212 KB
testcase_01	AC	87 ms; 34,212 KB
testcase_02	AC	88 ms; 34,212 KB
testcase_03	AC	87 ms; 34,212 KB
testcase_04	AC	88 ms; 34,212 KB
testcase_05	AC	88 ms; 34,212 KB
testcase_06	AC	87 ms; 34,340 KB
testcase_07	AC	87 ms; 34,340 KB
testcase_08	AC	92 ms; 34,212 KB
testcase_09	AC	88 ms; 34,212 KB
testcase_10	AC	87 ms; 34,212 KB
testcase_11	AC	99 ms; 37,796 KB
testcase_12	AC	113 ms; 41,892 KB
testcase_13	AC	239 ms; 63,012 KB
testcase_14	AC	264 ms; 62,884 KB
testcase_15	AC	222 ms; 60,580 KB
testcase_16	AC	616 ms; 62,116 KB
testcase_17	AC	656 ms; 62,116 KB
testcase_18	AC	400 ms; 59,428 KB
testcase_19	AC	205 ms; 211,380 KB

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (100 ms)。
MSBuild のバージョン 17.7.3+8ec440e68 (.NET)
  main -> /home/judge/data/code/bin/Release/net7.0/main.dll
  main -> /home/judge/data/code/bin/Release/net7.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));
    }
}