ABC128-E Roadwork

問題へのリンク

C++のソース

#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <vector>

std::vector<std::string> GetInputValues();

std::string InputPattern = "InputX";

std::vector<std::string> GetInputValues()
{
    std::vector<std::string> InputValuesVect;

    if (InputPattern == "Input1") {
        InputValuesVect.push_back("4 6");
        InputValuesVect.push_back("1 3 2");
        InputValuesVect.push_back("7 13 10");
        InputValuesVect.push_back("18 20 13");
        InputValuesVect.push_back("3 4 2");
        InputValuesVect.push_back("0");
        InputValuesVect.push_back("1");
        InputValuesVect.push_back("2");
        InputValuesVect.push_back("3");
        InputValuesVect.push_back("5");
        InputValuesVect.push_back("8");
    }
    else { //実際の入力
        while (true) {
            std::string wkStr;
            std::getline(std::cin, wkStr);
            if (std::cin.eof()) break;
            InputValuesVect.push_back(wkStr.c_str());
        }
    }

    return InputValuesVect;
}

struct STXInfoDef
{
    int S;
    int T;
    int X;

    bool operator<(const STXInfoDef& right) const {
        return X < right.X;
    }
};

int main()
{
    std::vector<std::string> InputVect = GetInputValues();

    int N;
    int SpaceInd = InputVect.at(0).find_first_of(" ");

    std::istringstream iss1(InputVect.at(0).substr(0, SpaceInd));
    iss1 >> N;

    std::vector<STXInfoDef> STXInfoVect;
    for (int I = 1; I <= N; I++) {
        std::vector<int> NumVect;
        std::istringstream iss3(InputVect.at(I));
        while (iss3.eof() == false) {
            int wkInt;
            iss3 >> wkInt;
            NumVect.push_back(wkInt);
        }

        STXInfoDef WillAdd;
        WillAdd.S = NumVect.at(0);
        WillAdd.T = NumVect.at(1) - 1; // 開区間を閉区間に変更するのでマイナス1
        WillAdd.X = NumVect.at(2);

        WillAdd.S -= WillAdd.X;
        WillAdd.T -= WillAdd.X;

        if (WillAdd.S < 0) {
            WillAdd.S = 0;
        }
        STXInfoVect.push_back(WillAdd);
    }

    std::vector<int> DVect;
    std::set<int> DSet;
    for (int I = N + 1; I <= (int)InputVect.size() - 1; I++) {
        int D = atoi(InputVect.at(I).c_str());
        DVect.push_back(D);
        DSet.insert(D);
    }

    sort(STXInfoVect.begin(), STXInfoVect.end());
    std::map<int, int> AnswerMap;

    for (int I = 0; I <= (int)STXInfoVect.size() - 1; I++) {
        int S = STXInfoVect[I].S;
        int T = STXInfoVect[I].T;
        int X = STXInfoVect[I].X;

        std::set<int>::iterator it = DSet.lower_bound(S);
        std::vector<int> RemoveVect;
        while (it != DSet.end()) {
            int D = (*it);
            if (T < D) break;

            //printf("%dは工事場所%dでストップ\n", D, X);
            AnswerMap[D] = X;

            RemoveVect.push_back(D);
            it++;
        }
        for (int I = 0; I <= (int)RemoveVect.size() - 1; I++) {
            DSet.erase(RemoveVect[I]);
        }
    }

    for (int I = 0; I <= (int)DVect.size() - 1; I++) {
        int CurrD = DVect.at(I);
        if (AnswerMap.find(CurrD) != AnswerMap.end()) {
            printf("%d\n", AnswerMap[CurrD]);
        }
        else {
            puts("-1");
        }
    }
}

C#のソース(RBSTでC++のsetを模倣する方法)

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("4 6");
            WillReturn.Add("1 3 2");
            WillReturn.Add("7 13 10");
            WillReturn.Add("18 20 13");
            WillReturn.Add("3 4 2");
            WillReturn.Add("0");
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("3");
            WillReturn.Add("5");
            WillReturn.Add("8");
            //2
            //2
            //10
            //-1
            //13
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    class BlockInfoDef
    {
        internal int RangeSta;
        internal int RangeEnd;
        internal int BlockPos;
    }

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

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        int N = wkArr[0];

        var BlockInfoList = new List<BlockInfoDef>();
        foreach (string EachStr in InputList.Skip(1).Take(N)) {
            SplitAct(EachStr);
            BlockInfoDef WillAdd = new BlockInfoDef();
            WillAdd.RangeSta = wkArr[0];
            WillAdd.RangeEnd = wkArr[1] - 1; // 開区間を閉区間に変更するのでマイナス1
            WillAdd.BlockPos = wkArr[2];

            WillAdd.RangeSta -= WillAdd.BlockPos;
            WillAdd.RangeEnd -= WillAdd.BlockPos;

            if (WillAdd.RangeSta < 0) {
                WillAdd.RangeSta = 0;
            }
            BlockInfoList.Add(WillAdd);
        }
        int[] DArr = InputList.Skip(1 + N).Select(pX => int.Parse(pX)).ToArray();

        var Ins_CPP_Set = new CPP_Set<int>();
        Array.ForEach(DArr, pX => Ins_CPP_Set.Insert(pX));

        var Query = BlockInfoList.OrderBy(pX => pX.BlockPos).ThenBy(pX => pX.RangeSta).ToList();

        var AnswerDict = new Dictionary<int, int>();
        foreach (BlockInfoDef EachBlockInfo in Query) {
            int LB = Ins_CPP_Set.LowerBound(EachBlockInfo.RangeSta);
            if (Ins_CPP_Set.IsValidInd(LB) == false) continue;

            var RemoveList = new List<int>();
            for (int I = Ins_CPP_Set.LowerBound(EachBlockInfo.RangeSta); I <= Ins_CPP_Set.Count() - 1; I++) {
                int EachKey = Ins_CPP_Set[I];

                if (EachBlockInfo.RangeEnd < EachKey) break;

                if (EachBlockInfo.RangeSta <= EachKey && EachKey <= EachBlockInfo.RangeEnd) {
                    AnswerDict[EachKey] = EachBlockInfo.BlockPos;
                    RemoveList.Add(EachKey);
                }
            }
            RemoveList.ForEach(pX => Ins_CPP_Set.Remove(pX));
        }

        var sb = new System.Text.StringBuilder();
        foreach (int EachD in DArr) {
            if (AnswerDict.ContainsKey(EachD)) {
                sb.AppendLine(AnswerDict[EachD].ToString());
            }
            else {
                sb.AppendLine("-1");
            }
        }
        Console.Write(sb.ToString());
    }
}

#region CPP_Set_MultiSet
// Self-Balancing Binary Search Tree
// (using Randamized BST)
internal class SB_BinarySearchTree<T> where T : IComparable
{
    internal class Node
    {
        internal T Value;
        internal Node LChild;
        internal Node RChild;
        internal int Count; // 部分木のサイズ

        internal Node(T v)
        {
            Value = v;
            Count = 1;
        }
    }

    static Random _rnd = new Random();

    internal static int Count(Node t)
    {
        return t == null ? 0 : t.Count;
    }

    static Node Update(Node t)
    {
        t.Count = Count(t.LChild) + Count(t.RChild) + 1;
        return t;
    }

    internal static Node Merge(Node l, Node r)
    {
        if (l == null || r == null) return l == null ? r : l;

        if ((double)Count(l) / (double)(Count(l) + Count(r)) > _rnd.NextDouble()) {
            l.RChild = Merge(l.RChild, r);
            return Update(l);
        }
        r.LChild = Merge(l, r.LChild);
        return Update(r);
    }

    // C#4.0のTuppleクラスもどき
    internal struct CS4_Tupple_Node
    {
        internal Node mItem1;
        internal Node mItem2;

        internal CS4_Tupple_Node(Node pItem1, Node pItem2)
        {
            mItem1 = pItem1;
            mItem2 = pItem2;
        }
    }

    // split as [0, k), [k, n)
    internal static CS4_Tupple_Node Split(Node t, int k)
    {
        if (t == null) return new CS4_Tupple_Node(null, null);
        if (k <= Count(t.LChild)) {
            CS4_Tupple_Node s = Split(t.LChild, k);
            t.LChild = s.mItem2;
            return new CS4_Tupple_Node(s.mItem1, Update(t));
        }
        else {
            CS4_Tupple_Node s = Split(t.RChild, k - Count(t.LChild) - 1);
            t.RChild = s.mItem1;
            return new CS4_Tupple_Node(Update(t), s.mItem2);
        }
    }

    internal static Node Remove(Node t, T v)
    {
        if (Find(t, v) == null) return t;
        return RemoveAt(t, LowerBound(t, v));
    }

    internal static Node RemoveAt(Node t, int k)
    {
        CS4_Tupple_Node s = Split(t, k);
        CS4_Tupple_Node s2 = Split(s.mItem2, 1);
        return Merge(s.mItem1, s2.mItem2);
    }

    internal static bool Contains(Node t, T v)
    {
        return Find(t, v) != null;
    }

    internal static Node Find(Node t, T v)
    {
        while (t != null) {
            int cmp = t.Value.CompareTo(v);
            if (cmp > 0) t = t.LChild;
            else if (cmp < 0) t = t.RChild;
            else break;
        }
        return t;
    }

    internal static Node FindByIndex(Node t, int idx)
    {
        if (t == null) return null;

        int currentIdx = Count(t) - Count(t.RChild) - 1;
        while (t != null) {
            if (currentIdx == idx) return t;
            if (currentIdx > idx) {
                t = t.LChild;
                currentIdx -= (Count(t == null ? null : t.RChild) + 1);
            }
            else {
                t = t.RChild;
                currentIdx += (Count(t == null ? null : t.LChild) + 1);
            }
        }
        return null;
    }

    internal static int UpperBound(Node t, T v)
    {
        Node torg = t;
        if (t == null) return -1;

        int ret = int.MaxValue;
        int idx = Count(t) - Count(t.RChild) - 1;
        while (t != null) {
            int cmp = t.Value.CompareTo(v);

            if (cmp > 0) {
                ret = Math.Min(ret, idx);
                t = t.LChild;
                idx -= (Count(t == null ? null : t.RChild) + 1);
            }
            else if (cmp <= 0) {
                t = t.RChild;
                idx += (Count(t == null ? null : t.LChild) + 1);
            }
        }
        return ret == int.MaxValue ? Count(torg) : ret;
    }

    internal static int LowerBound(Node t, T v)
    {
        Node torg = t;
        if (t == null) return -1;

        int idx = Count(t) - Count(t.RChild) - 1;
        int ret = int.MaxValue;
        while (t != null) {
            int cmp = t.Value.CompareTo(v);
            if (cmp >= 0) {
                if (cmp == 0) ret = Math.Min(ret, idx);
                t = t.LChild;
                if (t == null) ret = Math.Min(ret, idx);
                idx -= t == null ? 0 : (Count(t.RChild) + 1);
            }
            else if (cmp < 0) {
                t = t.RChild;
                idx += (Count(t == null ? null : t.LChild) + 1);
                if (t == null) return idx;
            }
        }
        return ret == int.MaxValue ? Count(torg) : ret;
    }

    internal static Node Insert(Node t, T v)
    {
        int ub = LowerBound(t, v);
        return InsertByIdx(t, ub, v);
    }

    static Node InsertByIdx(Node t, int k, T v)
    {
        CS4_Tupple_Node s = Split(t, k);
        return Merge(Merge(s.mItem1, new Node(v)), s.mItem2);
    }

    internal static IEnumerable<T> EnumerateList(Node t)
    {
        var ret = new List<T>();
        EnumerateList(t, ret);
        return ret;
    }

    static void EnumerateList(Node t, List<T> ret)
    {
        if (t == null) return;
        EnumerateList(t.LChild, ret);
        ret.Add(t.Value);
        EnumerateList(t.RChild, ret);
    }

    internal static IEnumerable<T> EnumerateYield(Node t)
    {
        if (t != null) {
            foreach (var Each in EnumerateYield(t.LChild)) {
                yield return Each;
            }
            yield return t.Value;
            foreach (var Each in EnumerateYield(t.RChild)) {
                yield return Each;
            }
        }
    }
}

// CPP-Like Set
internal class CPP_Set<T> where T : IComparable
{
    protected SB_BinarySearchTree<T>.Node _root;

    // 機能01 インデクサ(0オリジン)
    internal T this[int idx] { get { return ElementAt(idx); } }

    // 機能02 件数を返す
    internal int Count()
    {
        return SB_BinarySearchTree<T>.Count(_root);
    }

    // 機能03 要素を追加
    internal virtual void Insert(T v)
    {
        if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
        else {
            if (SB_BinarySearchTree<T>.Find(_root, v) != null) return;
            _root = SB_BinarySearchTree<T>.Insert(_root, v);
        }
    }

    // 機能04 全ての要素を削除
    internal void Clear()
    {
        _root = null;
    }

    // 機能05 指定した要素があれば削除
    internal void Remove(T v)
    {
        _root = SB_BinarySearchTree<T>.Remove(_root, v);
    }

    // 機能06 指定した要素の有無を返す
    internal bool Contains(T v)
    {
        return SB_BinarySearchTree<T>.Contains(_root, v);
    }

    // 機能07 インデクサの糖衣構文
    internal T ElementAt(int k)
    {
        var node = SB_BinarySearchTree<T>.FindByIndex(_root, k);
        if (node == null) throw new IndexOutOfRangeException();
        return node.Value;
    }

    // 機能08 指定した値の件数を返す
    internal int Count(T v)
    {
        return SB_BinarySearchTree<T>.UpperBound(_root, v) -
               SB_BinarySearchTree<T>.LowerBound(_root, v);
    }

    // 機能09 引数以上の最小添字を返す
    internal int LowerBound(T v)
    {
        return SB_BinarySearchTree<T>.LowerBound(_root, v);
    }

    // 機能10 引数超えの最小添字を返す
    internal int UpperBound(T v)
    {
        return SB_BinarySearchTree<T>.UpperBound(_root, v);
    }

    // C#4.0のTuppleクラスもどき
    internal struct CS4_Tupple_Int
    {
        internal int mItem1;
        internal int mItem2;

        internal CS4_Tupple_Int(int pItem1, int pItem2)
        {
            mItem1 = pItem1;
            mItem2 = pItem2;
        }
    }

    // 機能11 引数に等しい範囲の下限と上限を返す
    internal CS4_Tupple_Int EqualRange(T v)
    {
        if (!Contains(v)) return new CS4_Tupple_Int(-1, -1);
        return new CS4_Tupple_Int(SB_BinarySearchTree<T>.LowerBound(_root, v),
                                  SB_BinarySearchTree<T>.UpperBound(_root, v) - 1);
    }

    // 機能12 Listを作って返す
    internal List<T> ToList()
    {
        return new List<T>(SB_BinarySearchTree<T>.EnumerateList(_root));
    }

    // 機能13 Listでなく列挙を返す
    internal IEnumerable<T> EnumerateYield()
    {
        return SB_BinarySearchTree<T>.EnumerateYield(_root);
    }

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

// CPP-Like multiset
internal class CPP_MultiSet<T> : CPP_Set<T> where T : IComparable
{
    internal override void Insert(T v)
    {
        if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
        else _root = SB_BinarySearchTree<T>.Insert(_root, v);
    }
}
#endregion

C#のソース(AVL木でC++のsetを模倣する方法)

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("4 6");
            WillReturn.Add("1 3 2");
            WillReturn.Add("7 13 10");
            WillReturn.Add("18 20 13");
            WillReturn.Add("3 4 2");
            WillReturn.Add("0");
            WillReturn.Add("1");
            WillReturn.Add("2");
            WillReturn.Add("3");
            WillReturn.Add("5");
            WillReturn.Add("8");
            //2
            //2
            //10
            //-1
            //13
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    class BlockInfoDef
    {
        internal int RangeSta;
        internal int RangeEnd;
        internal int BlockPos;
    }

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

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        int N = wkArr[0];

        var BlockInfoList = new List<BlockInfoDef>();
        foreach (string EachStr in InputList.Skip(1).Take(N)) {
            SplitAct(EachStr);
            BlockInfoDef WillAdd = new BlockInfoDef();
            WillAdd.RangeSta = wkArr[0];
            WillAdd.RangeEnd = wkArr[1] - 1; // 開区間を閉区間に変更するのでマイナス1
            WillAdd.BlockPos = wkArr[2];

            WillAdd.RangeSta -= WillAdd.BlockPos;
            WillAdd.RangeEnd -= WillAdd.BlockPos;

            if (WillAdd.RangeSta < 0) {
                WillAdd.RangeSta = 0;
            }
            BlockInfoList.Add(WillAdd);
        }
        int[] DArr = InputList.Skip(1 + N).Select(pX => int.Parse(pX)).ToArray();

        var Ins_AVL_Set = new AVL_Set_MultiSet<int>();
        Array.ForEach(DArr, pX => Ins_AVL_Set.Add(pX));

        var Query = BlockInfoList.OrderBy(pX => pX.BlockPos).ThenBy(pX => pX.RangeSta).ToList();

        var AnswerDict = new Dictionary<int, int>();
        foreach (BlockInfoDef EachBlockInfo in Query) {
            var RemoveList = new List<int>();
            int LB = Ins_AVL_Set.LowerBound(EachBlockInfo.RangeSta);
            if (Ins_AVL_Set.IsValidInd(LB) == false) continue;
            for (int I = Ins_AVL_Set.LowerBound(EachBlockInfo.RangeSta); I <= Ins_AVL_Set.Count - 1; I++) {
                int EachKey = Ins_AVL_Set[I];

                if (EachBlockInfo.RangeEnd < EachKey) break;

                if (EachBlockInfo.RangeSta <= EachKey && EachKey <= EachBlockInfo.RangeEnd) {
                    AnswerDict[EachKey] = EachBlockInfo.BlockPos;
                    RemoveList.Add(EachKey);
                }
            }
            RemoveList.ForEach(pX => Ins_AVL_Set.Remove(pX));
        }

        var sb = new System.Text.StringBuilder();
        foreach (int EachD in DArr) {
            if (AnswerDict.ContainsKey(EachD)) {
                sb.AppendLine(AnswerDict[EachD].ToString());
            }
            else {
                sb.AppendLine("-1");
            }
        }
        Console.Write(sb.ToString());
    }
}

#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[int index] { get { return find(root, index); } }
    internal int Count { get { return root.Count; } }

    internal void RemoveAt(int 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];
            int k = 0;
            walk(root, ret, ref k);
            return ret;
        }
    }

    private void walk(Node t, T[] a, ref int 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, int k)
    {
        int 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)
    {
        int 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, int 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 int LowerBound(T v)
    {
        int 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 int UpperBound(T v)
    {
        int 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;
        }
    }

    // 追加機能 V未満で最大の要素の番号を返す
    internal int Lower_Max(T v)
    {
        int UpperB = UpperBound(v);
        if (IsValidInd(UpperB - 1)) {
            return UpperB - 1;
        }
        return -1;
    }

    // 追加機能 V以下で最大の要素の番号を返す
    internal int LowerOrEqual_Max(T v)
    {
        int LowerB = LowerBound(v);
        if (IsValidInd(LowerB - 1)) {
            return LowerB - 1;
        }
        return -1;
    }

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

    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 int Count { get; private set; }
        internal int 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

解説

平衡二分探索木でストップ対象になる人を管理しつつ、
座標の小さい工事場所から
この工事でストップになる人をチェックしてます。