ABC-077-C Snuke Festival

■■■問題■■■

今年もすぬけ祭の季節がやってきました。
りんごさんは、まず手始めにすぬけ君召喚の儀式を執り行おうと思っています。
儀式には祭壇が必要で、祭壇は上部、中部、下部の3つのカテゴリーのパーツ1つずつからなります。

祭壇の3カテゴリーのパーツがそれぞれN個ずつあります。
i個目の上部のパーツのサイズはAi、
i個目の中部のパーツのサイズはBi、
i個目の下部のパーツのサイズはCiです。

祭壇を作るにあたっては、
中部のパーツのサイズは上部のパーツのサイズより真に大きく、
下部のパーツのサイズは中部のパーツのサイズより真に大きくなければなりません。
逆に、この条件を満たす任意の3つのピースを組み合わせて祭壇を作ることができます。

りんごさんが作ることのできる祭壇は何種類あるでしょうか。
ただし、2つの祭壇が異なるとは、上部、中部、下部に使われるピースのうち
少なくとも1つが異なることを言います。

■■■入力■■■

N
A1 ・・・ AN
B1 ・・・ BN
C1 ・・・ CN

●1 <= N <= 10万
●1 <= Ai <= 10億(1 <= i <= N)
●1 <= Bi <= 10億(1 <= i <= N)
●1 <= Ci <= 10億(1 <= i <= N)
●入力は全て整数である

■■■出力■■■

りんごさんが作ることのできる祭壇の種類数を出力せよ

C#のソース(2分法を使う方法)

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("2");
            WillReturn.Add("1 5");
            WillReturn.Add("2 4");
            WillReturn.Add("3 6");
            //3
            //次の3種類の祭壇があります。
            //●上部に1個目、中部に1個目、下部に1個目のパーツを使った祭壇
            //●上部に1個目、中部に1個目、下部に2個目のパーツを使った祭壇
            //●上部に1個目、中部に2個目、下部に2個目のパーツを使った祭壇
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("1 1 1");
            WillReturn.Add("2 2 2");
            WillReturn.Add("3 3 3");
            //27
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6");
            WillReturn.Add("3 14 159 2 6 53");
            WillReturn.Add("58 9 79 323 84 6");
            WillReturn.Add("2643 383 2 79 50 288");
            //87
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int UB;

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

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

        SplitAct(InputList[1]);
        int[] AArr = wkArr;
        UB = AArr.GetUpperBound(0);

        SplitAct(InputList[2]);
        int[] BArr = wkArr;

        SplitAct(InputList[3]);
        int[] CArr = wkArr;

        Array.Sort(AArr);
        Array.Sort(BArr);
        Array.Sort(CArr);

        long Answer = 0;
        foreach (int EachInt in BArr) {
            int wkInd1 = ExecNibunhou1(AArr, EachInt);
            long CurrCnt = wkInd1 + 1;

            int wkInd2 = ExecNibunhou2(CArr, EachInt);
            CurrCnt *= (UB - wkInd2 + 1);

            Answer += CurrCnt;
        }
        Console.WriteLine(Answer);
    }

    //2分法で指定した値未満の最大の添字を求める
    static int ExecNibunhou1(int[] pArr, int pVal)
    {
        if (pArr[0] >= pVal) return -1;
        if (pArr[UB] < pVal) return UB;

        int L = 0;
        int R = UB;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            bool IsOK = (pArr[Mid] < pVal);
            if (IsOK) L = Mid;
            else R = Mid;
        }
        return L;
    }

    //2分法で指定した値超えの最小の添字を求める
    static int ExecNibunhou2(int[] pArr, int pVal)
    {
        if (pArr[0] > pVal) return 0;
        if (pArr[UB] <= pVal) return UB + 1;

        int L = 0;
        int R = UB;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            bool IsOK = (pArr[Mid] > pVal);
            if (IsOK) R = Mid;
            else L = Mid;
        }
        return R;
    }
}

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>();

        string wkStr;
        while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        return WillReturn;
    }

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

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

        SplitAct(InputList[1]);
        int[] AArr = wkArr;
        int UB = AArr.GetUpperBound(0);

        SplitAct(InputList[2]);
        int[] BArr = wkArr;

        SplitAct(InputList[3]);
        int[] CArr = wkArr;

        Array.Sort(AArr);
        Array.Sort(BArr);
        Array.Sort(CArr);

        //尺取法で、自分未満な配列Aの要素数[配列Bの添字]を求める
        int[] LowerCntArrA = new int[UB + 1];
        int J = 0;
        for (int I = 0; I <= UB; I++) {
            while (J <= UB && BArr[I] > AArr[J]) J++;
            LowerCntArrA[I] = J;
        }

        //尺取法で、自分以下な配列Cの要素数[配列Bの添字]を求める
        int[] LowerCntArrC = new int[UB + 1];
        J = 0;
        for (int I = 0; I <= UB; I++) {
            while (J <= UB && BArr[I] >= CArr[J]) J++;
            LowerCntArrC[I] = J;
        }

        long Answer = 0;
        for (int I = 0; I <= UB; I++) {
            Answer += (long)LowerCntArrA[I] * (CArr.Length - LowerCntArrC[I]);
        }
        Console.WriteLine(Answer);
    }
}

解説

真ん中を全探索しつつ、上下を2分探索して、
積の法則を使ってます。