結果

問題 No.674 n連勤
ユーザー Risen
提出日時 2024-03-28 23:28:32
言語 C#
(.NET 8.0.404)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /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/

ソースコード

diff #
プレゼンテーションモードにする

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));
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0