ARC182-A Chmax Rush!

問題へのリンク

C#のソース

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("8 3");
            WillReturn.Add("1 8");
            WillReturn.Add("8 1");
            WillReturn.Add("2 1");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("8 3");
            WillReturn.Add("8 1");
            WillReturn.Add("1 8");
            WillReturn.Add("1 2");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("241 82");
            WillReturn.Add("190 3207371");
            WillReturn.Add("229 3639088");
            WillReturn.Add("61 4428925");
            WillReturn.Add("84 17258698");
            WillReturn.Add("34 42692503");
            WillReturn.Add("207 59753183");
            WillReturn.Add("180 67198566");
            WillReturn.Add("78 99285033");
            WillReturn.Add("60 102449991");
            WillReturn.Add("234 122146510");
            WillReturn.Add("111 126959145");
            WillReturn.Add("141 152331579");
            WillReturn.Add("78 159855439");
            WillReturn.Add("11 169658471");
            WillReturn.Add("22 189991287");
            WillReturn.Add("37 204602946");
            WillReturn.Add("73 209329065");
            WillReturn.Add("72 215363269");
            WillReturn.Add("152 236450854");
            WillReturn.Add("175 237822921");
            WillReturn.Add("22 261431608");
            WillReturn.Add("144 252550201");
            WillReturn.Add("54 268889550");
            WillReturn.Add("238 276997357");
            WillReturn.Add("69 313065279");
            WillReturn.Add("226 330144323");
            WillReturn.Add("6 335788783");
            WillReturn.Add("126 345410019");
            WillReturn.Add("220 348318997");
            WillReturn.Add("166 365778763");
            WillReturn.Add("142 382251905");
            WillReturn.Add("200 406191336");
            WillReturn.Add("234 392702679");
            WillReturn.Add("83 409660987");
            WillReturn.Add("183 410908761");
            WillReturn.Add("142 445707116");
            WillReturn.Add("205 470279207");
            WillReturn.Add("230 486436406");
            WillReturn.Add("156 494269002");
            WillReturn.Add("113 495687706");
            WillReturn.Add("200 500005738");
            WillReturn.Add("162 505246499");
            WillReturn.Add("201 548652987");
            WillReturn.Add("86 449551554");
            WillReturn.Add("62 459527873");
            WillReturn.Add("32 574001635");
            WillReturn.Add("230 601073337");
            WillReturn.Add("175 610244315");
            WillReturn.Add("174 613857555");
            WillReturn.Add("181 637452273");
            WillReturn.Add("158 637866397");
            WillReturn.Add("148 648101378");
            WillReturn.Add("172 646898076");
            WillReturn.Add("144 682578257");
            WillReturn.Add("239 703460335");
            WillReturn.Add("192 713255331");
            WillReturn.Add("28 727075136");
            WillReturn.Add("196 730768166");
            WillReturn.Add("111 751850547");
            WillReturn.Add("90 762445737");
            WillReturn.Add("204 762552166");
            WillReturn.Add("72 773170159");
            WillReturn.Add("240 803415865");
            WillReturn.Add("32 798873367");
            WillReturn.Add("195 814999380");
            WillReturn.Add("72 842641864");
            WillReturn.Add("125 851815348");
            WillReturn.Add("116 858041919");
            WillReturn.Add("200 869948671");
            WillReturn.Add("195 873324903");
            WillReturn.Add("5 877767414");
            WillReturn.Add("105 877710280");
            WillReturn.Add("150 877719360");
            WillReturn.Add("9 884707717");
            WillReturn.Add("230 880263190");
            WillReturn.Add("88 967344715");
            WillReturn.Add("49 977643789");
            WillReturn.Add("167 979463984");
            WillReturn.Add("70 981400941");
            WillReturn.Add("114 991068035");
            WillReturn.Add("94 991951735");
            WillReturn.Add("141 995762200");
            //682155965
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct PVInfoDef
    {
        internal long Pivot;
        internal long Value;
        internal HashSet<char> OKSet;
    }
    static List<PVInfoDef> mPVInfoList = new List<PVInfoDef>();

    const long Hou = 998244353;

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

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

        SplitAct(InputList[0]);
        long N = wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            PVInfoDef WillAdd;
            WillAdd.Pivot = wkArr[0];
            WillAdd.Value = wkArr[1];
            WillAdd.OKSet = new HashSet<char> { 'L', 'R' };
            mPVInfoList.Add(WillAdd);
        }
        int UB = mPVInfoList.Count - 1;

        for (int I = 0; I <= UB; I++) {
            long CurrPivot = mPVInfoList[I].Pivot;
            long CurrValue = mPVInfoList[I].Value;

            // LをRemove
            for (int J = I + 1; J <= UB; J++) {
                if (CurrValue <= mPVInfoList[J].Value) continue;

                if (CurrPivot >= mPVInfoList[J].Pivot) {
                    mPVInfoList[I].OKSet.Remove('L');
                    mPVInfoList[J].OKSet.Remove('R');
                }
            }

            // RをRemove
            for (int J = I + 1; J <= UB; J++) {
                if (CurrValue <= mPVInfoList[J].Value) continue;

                if (CurrPivot <= mPVInfoList[J].Pivot) {
                    mPVInfoList[I].OKSet.Remove('R');
                    mPVInfoList[J].OKSet.Remove('L');
                }
            }
        }

        long Answer = 1;
        foreach (PVInfoDef EachPVInfo in mPVInfoList) {
            Answer *= EachPVInfo.OKSet.Count;
            Answer %= Hou;
        }
        Console.WriteLine(Answer);
    }
}

解説

問題を要約すると、
[1,軸] または [軸,UB]まで
の2つの区間の、どっちかを区間更新することの選択の繰り返しが
何通りかを調べる問題になります。

後続の更新値が、自分以上なら無視してよいですが
後続の更新値が、自分未満の場合は、
更新できる区間に縛りがかかります。

後は、最後に積の法則を使えば良いです。