#1195236 (C#(csc)) No.674 n連勤

• 問題: No.674 n連勤
• ユーザー: aketijyuuzou
• 提出日時: 2026-10-24 19:57:49
• 言語: C#(csc) (csc 3.9.0)
• 結果: WA
• 実行時間: -
• コード長: 16,140 bytes
• コンパイル時間: 3,631 ms
• コンパイル使用メモリ: 120,408 KB
• 実行使用メモリ: 35,092 KB
• 最終ジャッジ日時: 2026-10-24 19:57:58
• 合計ジャッジ時間: 8,359 ms
• ジャッジサーバーID （参考情報）: judge7_0 / judge5_0

ファイルパターン	結果
sample	AC * 3
other	AC * 11 WA * 6

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("10 3");
            WillReturn.Add("0 1");
            WillReturn.Add("6 8");
            WillReturn.Add("2 7");
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 4");
            WillReturn.Add("3 7");
            WillReturn.Add("3 5");
            WillReturn.Add("1 1");
            WillReturn.Add("4 9");
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1000000000000000000 2");
            WillReturn.Add("0 999999999999999999");
            WillReturn.Add("0 999999999999999999");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        var InsIntervalSet = new IntervalSet();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long L = wkArr[0];
            long R = wkArr[1];
            InsIntervalSet.AddInterval(L, R);
            Console.WriteLine(InsIntervalSet.mMaxLen);
        }
        var wkList = InsIntervalSet.GetIntervalInfoList();
    }
}

// 区間をsetで管理するテク
#region IntervalSet
// IntervalSetクラス
internal class IntervalSet
{
    internal struct IntervalInfoDef
    {
        internal long IntervalSta;
        internal long IntervalEnd;
    }

    internal long mMaxLen = 0;

    // 区間StaのAVL木
    private AVL_Set_MultiSet<long> mIntervalStaSet;

    // 区間End[区間Sta]なDict
    private Dictionary<long, long> mIntervalEndDict;

    // コンストラクタ
    internal IntervalSet()
    {
        mIntervalStaSet = new AVL_Set_MultiSet<long>();
        mIntervalStaSet.IsMultiSet = true;

        mIntervalEndDict = new Dictionary<long, long>();
    }

    // 区間を追加
    internal void AddInterval(long pSta, long pEnd)
    {
        // どの区間ともOverlapしてない場合
        if (IsOverlapInterval(pSta, pEnd) == false) {
            mIntervalStaSet.Add(pSta);
            mIntervalEndDict[pSta] = pEnd;
            mMaxLen = Math.Max(mMaxLen, pEnd - pSta + 1);
            return;
        }

        // Overlapの上限
        long AVLIndEnd = mIntervalStaSet.LowerOrEqual_Max(pEnd);

        var WillRemoveIndList = new List<long>();
        var WillRemoveStaList = new List<long>();
        long MergedIntervalSta = pSta;
        long MergedIntervalEnd = pEnd;

        for (long I = AVLIndEnd; 0 <= I; I--) {
            long CurrIntervalSta = mIntervalStaSet[I];
            long CurrIntervalEnd = mIntervalEndDict[CurrIntervalSta];

            if (IsOverlap_2_Interval(
                CurrIntervalSta, CurrIntervalEnd,
                MergedIntervalSta, MergedIntervalEnd)) {
                MergedIntervalSta = Math.Min(MergedIntervalSta, CurrIntervalSta);
                MergedIntervalEnd = Math.Max(MergedIntervalEnd, CurrIntervalEnd);
                WillRemoveIndList.Add(I);
                WillRemoveStaList.Add(CurrIntervalSta);
            }
            else break;
        }

        // 降順にRemove
        WillRemoveIndList.ForEach(pX => mIntervalStaSet.RemoveAt(pX));
        WillRemoveStaList.ForEach(pX => mIntervalEndDict.Remove(pX));

        // マージした区間を追加
        mIntervalStaSet.Add(MergedIntervalSta);
        mIntervalEndDict[MergedIntervalSta] = MergedIntervalEnd;

        mMaxLen = Math.Max(mMaxLen, MergedIntervalEnd - MergedIntervalSta + 1);
    }

    // Intervalの大小チェック
    private void IntervalCheck(long pSta, long pEnd)
    {
        if (pSta > pEnd) throw new Exception("pSta > pEnd");
    }

    // 引数の点を含む区間の存在判定
    internal bool IsOverlapPoint(long pPoint)
    {
        return IsOverlapInterval(pPoint, pPoint);
    }

    // 引数の区間とOverlapする区間の存在判定
    internal bool IsOverlapInterval(long pSta, long pEnd)
    {
        IntervalCheck(pSta, pEnd);

        long AVLInd = mIntervalStaSet.LowerOrEqual_Max(pEnd);

        if (mIntervalStaSet.IsValidInd(AVLInd) == false) {
            return false;
        }

        long KouhoSta = mIntervalStaSet[AVLInd];
        long KouhoEnd = mIntervalEndDict[KouhoSta];

        return IsOverlap_2_Interval(pSta, pEnd, KouhoSta, KouhoEnd);
    }

    // 区間2つを引数とし、Overlap有無を返す
    private bool IsOverlap_2_Interval(long pSta1, long pEnd1, long pSta2, long pEnd2)
    {
        return pSta1 - 1 <= pEnd2 && pSta2 - 1 <= pEnd1;
    }

    // 区間の配列を返す
    internal List<IntervalInfoDef> GetIntervalInfoList()
    {
        List<IntervalInfoDef> IntervalInfoList = new List<IntervalInfoDef>();

        long[] IntervalStaArr = mIntervalStaSet.Items;
        foreach (long EachIntervalSta in IntervalStaArr) {
            IntervalInfoDef WillAdd;
            WillAdd.IntervalSta = EachIntervalSta;
            WillAdd.IntervalEnd = mIntervalEndDict[EachIntervalSta];
            IntervalInfoList.Add(WillAdd);
        }
        return IntervalInfoList;
    }
}
#endregion

#region AVL_Set_MultiSet
/// <summary>
/// 要素の追加、削除、検索、取得が可能な集合を表します．
/// </summary>
/// <typeparam name="T">優先度付きキュー内の要素の型を指定します．</typeparam>
/// <remarks>内部的にはAVL木によって実装されています．</remarks>
internal class AVL_Set_MultiSet<T>
{
    Node root;
    readonly IComparer<T> comparer;
    readonly Node nil;

    /// <summary>
    /// 多重集合かどうかを表します．
    /// </summary>
    internal bool IsMultiSet { get; set; }
    internal AVL_Set_MultiSet(IComparer<T> comparer)
    {
        nil = new Node(default(T));
        root = nil;
        this.comparer = comparer;
    }

    internal AVL_Set_MultiSet() : this(Comparer<T>.Default) { }

    /// <summary>
    /// 要素をコレクションに追加します．
    /// </summary>
    /// <remarks>この操作は計算量 O(log N) で実行されます．</remarks>
    internal bool Add(T v)
    {
        return insert(ref root, v);
    }

    /// <summary>
    /// v が存在するならコレクションから削除します．
    /// </summary>
    /// <remarks>この操作は計算量 O(log N) で実行されます．</remarks>
    internal bool Remove(T v)
    {
        return remove(ref root, v);
    }

    /// <summary>
    /// 0-indexed で index 番目の要素をコレクションから取得します．
    /// </summary>
    /// <remarks>この操作は計算量 O(log N) で実行されます．</remarks>
    internal T this[long index] { get { return find(root, index); } }
    internal long Count { get { return root.Count; } }

    internal void RemoveAt(long k)
    {
        if (k < 0 || k >= root.Count) throw new ArgumentOutOfRangeException();
        removeAt(ref root, k);
    }

    /// <summary>
    /// このコレクションに含まれる要素を昇順に並べて返します．
    /// </summary>
    /// <remarks>この操作は計算量 O(N) で実行されます．</remarks>
    internal T[] Items
    {
        get
        {
            T[] ret = new T[root.Count];
            long k = 0;
            walk(root, ret, ref k);
            return ret;
        }
    }

    private void walk(Node t, T[] a, ref long k)
    {
        if (t.Count == 0) return;
        walk(t.lst, a, ref k);
        a[k++] = t.Key;
        walk(t.rst, a, ref k);
    }

    private bool insert(ref Node t, T key)
    {
        if (t.Count == 0) { t = new Node(key); t.lst = t.rst = nil; t.Update(); return true; }
        int cmp = comparer.Compare(t.Key, key);
        bool res;
        if (cmp > 0)
            res = insert(ref t.lst, key);
        else if (cmp == 0) {
            if (IsMultiSet) res = insert(ref t.lst, key);
            else return false;
        }
        else res = insert(ref t.rst, key);
        balance(ref t);
        return res;
    }

    private bool remove(ref Node t, T key)
    {
        if (t.Count == 0) return false;
        int cmp = comparer.Compare(key, t.Key);
        bool ret;
        if (cmp < 0) ret = remove(ref t.lst, key);
        else if (cmp > 0) ret = remove(ref t.rst, key);
        else {
            ret = true;
            var k = t.lst.Count;
            if (k == 0) { t = t.rst; return true; }
            if (t.rst.Count == 0) { t = t.lst; return true; }

            t.Key = find(t.lst, k - 1);
            removeAt(ref t.lst, k - 1);
        }
        balance(ref t);
        return ret;
    }

    private void removeAt(ref Node t, long k)
    {
        long cnt = t.lst.Count;
        if (cnt < k) removeAt(ref t.rst, k - cnt - 1);
        else if (cnt > k) removeAt(ref t.lst, k);
        else {
            if (cnt == 0) { t = t.rst; return; }
            if (t.rst.Count == 0) { t = t.lst; return; }

            t.Key = find(t.lst, k - 1);
            removeAt(ref t.lst, k - 1);
        }
        balance(ref t);
    }

    private void balance(ref Node t)
    {
        long balance = t.lst.Height - t.rst.Height;
        if (balance == -2) {
            if (t.rst.lst.Height - t.rst.rst.Height > 0) { rotR(ref t.rst); }
            rotL(ref t);
        }
        else if (balance == 2) {
            if (t.lst.lst.Height - t.lst.rst.Height < 0) rotL(ref t.lst);
            rotR(ref t);
        }
        else t.Update();
    }

    private T find(Node t, long k)
    {
        if (k < 0 || k > root.Count) throw new ArgumentOutOfRangeException();
        while (true) {
            if (k == t.lst.Count) return t.Key;
            else if (k < t.lst.Count) t = t.lst;
            else { k -= t.lst.Count + 1; t = t.rst; }
        }
    }
    /// <summary>
    /// コレクションに含まれる要素であって、 v 以上の最小の要素の番号を返します。
    /// </summary>
    /// <remarks>この操作は計算量 O(log N) で実行されます．</remarks>
    internal long LowerBound(T v)
    {
        // 追加機能 件数が0なら-1を返す
        if (this.Count == 0) {
            return -1;
        }

        // 追加機能 v 以上な要素が無い場合は-1を返す
        T MaxVal = this[this.Count - 1];
        int cmp = comparer.Compare(MaxVal, v);
        if (cmp == -1) return -1;

        long k = 0;
        Node t = root;
        while (true) {
            if (t.Count == 0) return k;
            if (comparer.Compare(v, t.Key) <= 0) t = t.lst;
            else { k += t.lst.Count + 1; t = t.rst; }
        }
    }
    /// <summary>
    /// コレクションに含まれる要素であって、 v より真に大きい、最小の要素の番号を返します。
    /// </summary>
    /// <remarks>この操作は計算量 O(log N) で実行されます．</remarks>
    internal long UpperBound(T v)
    {
        // 追加機能 件数が0なら-1を返す
        if (this.Count == 0) {
            return -1;
        }

        // 追加機能 v 超えな要素が無い場合は-1を返す
        T MaxVal = this[this.Count - 1];
        int cmp = comparer.Compare(MaxVal, v);
        if (cmp <= 0) return -1;

        long k = 0;
        Node t = root;
        while (true) {
            if (t.Count == 0) return k;
            if (comparer.Compare(t.Key, v) <= 0) { k += t.lst.Count + 1; t = t.rst; }
            else t = t.lst;
        }
    }

    // 追加機能01 V未満で最大の要素の番号を返す
    internal long Lower_Max(T v)
    {
        // 件数が0なら-1を返す
        if (this.Count == 0) {
            return -1;
        }

        // v 未満な要素が無い場合は-1を返す
        T MinVal = this[0];
        int cmp = comparer.Compare(MinVal, v);
        if (cmp >= 0) return -1;

        // v 以上の件数を調べる
        long More_Or_Equal_cnt = this.Count;
        long UB = this.Count - 1;
        long LowerB = LowerBound(v);
        if (IsValidInd(LowerB)) {
            More_Or_Equal_cnt -= (UB - LowerB + 1);
        }
        return More_Or_Equal_cnt - 1;
    }

    // 追加機能02 V以下で最大の要素の番号を返す
    internal long LowerOrEqual_Max(T v)
    {
        // 件数が0なら-1を返す
        if (this.Count == 0) {
            return -1;
        }

        // v 以下な要素が無い場合は-1を返す
        T MinVal = this[0];
        int cmp = comparer.Compare(MinVal, v);
        if (cmp > 0) return -1;

        // v 超えの件数を調べる
        long More_cnt = this.Count;
        long UB = this.Count - 1;
        long UpperB = UpperBound(v);
        if (IsValidInd(UpperB)) {
            More_cnt -= (UB - UpperB + 1);
        }
        return More_cnt - 1;
    }

    // 追加機能03 LowerBoundなどで返したIndが、有効範囲かを判定
    internal bool IsValidInd(long pInd)
    {
        if (pInd < 0) return false;
        if (this.Count <= pInd) return false;
        return true;
    }

    // 追加機能04 Vを含むかを返す
    internal bool Contains(T v)
    {
        long LowerB = LowerBound(v);
        if (IsValidInd(LowerB) == false) {
            return false;
        }
        int cmp = comparer.Compare(this[LowerB], v);
        return cmp == 0;
    }

    // 追加機能05 Min以上な値の個数を返す
    internal long GetMoreOrEqualCnt(T pMinVal)
    {
        long ResultInd = LowerBound(pMinVal);
        if (IsValidInd(ResultInd) == false) return 0;
        return Count - 1 - ResultInd + 1;
    }

    // 追加機能06 Min超えな値の個数を返す
    internal long GetMoreStrictCnt(T pMinVal)
    {
        long ResultInd = UpperBound(pMinVal);
        if (IsValidInd(ResultInd) == false) return 0;
        return Count - 1 - ResultInd + 1;
    }

    // 追加機能07 Max以下な値の個数を返す
    internal long GetLessOrEqualCnt(T pMaxVal)
    {
        long ResultInd = LowerOrEqual_Max(pMaxVal);

        if (IsValidInd(ResultInd) == false) return 0;
        return ResultInd + 1;
    }

    // 追加機能08 Max未満な値の個数を返す
    internal long GetLessStrictCnt(T pMaxVal)
    {
        long ResultInd = Lower_Max(pMaxVal);
        if (ResultInd == -1) return 0;
        return ResultInd + 1;
    }

    // 追加機能09 Min以上Max以下な値の個数を返す
    internal long GetRangeCnt(T pMinVal, T pMaxVal)
    {
        long ResultInd1 = LowerBound(pMinVal);
        if (IsValidInd(ResultInd1) == false) return 0;

        long ResultInd2 = LowerOrEqual_Max(pMaxVal);
        if (IsValidInd(ResultInd2) == false) return 0;

        if (ResultInd1 > ResultInd2) return 0;
        return ResultInd2 - ResultInd1 + 1;
    }

    private void rotR(ref Node t)
    {
        Node l = t.lst;
        t.lst = l.rst;
        l.rst = t;
        t.Update();
        l.Update();
        t = l;
    }

    private void rotL(ref Node t)
    {
        Node r = t.rst;
        t.rst = r.lst;
        r.lst = t;
        t.Update();
        r.Update();
        t = r;
    }

    class Node
    {
        internal Node(T key)
        {
            Key = key;
        }
        internal long Count { get; private set; }
        internal long Height { get; private set; }
        internal T Key { get; set; }
        internal Node lst, rst;
        internal void Update()
        {
            Count = 1 + lst.Count + rst.Count;
            Height = 1 + Math.Max(lst.Height, rst.Height);
        }
        public override string ToString()
        {
            return string.Format("Count = {0}, Key = {1}", Count, Key);
        }
    }
}
#endregion