Submission #3451852

---

Source Code Expand

using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
static long n = long.Parse(Console.ReadLine());
static long[] nums = new long[n];
static long[][] numsSub = new long[n][];
static long[] rightMin = new long[n];//長さがi+1のときの右端の最小値
static long answer = 1;
static long compareMemo = 0;

	static void Main()
	{
    for(long i = 0; i < n; i++)
    {
      numsSub[i] = new long[2];
      string[] input = Console.ReadLine().Split(' ');
  		numsSub[i][0] = long.Parse(input[0]);
  		numsSub[i][1] = long.Parse(input[1]);
    }
    Array.Sort(numsSub, (a, b) => a[0].CompareTo(b[0]));//xのみソート
    long minMemo = 0;//最小数
    long minMemoNum = -1;//最小数の更新回数
    for(long i = 0; i < n; i++)
    {
      if(numsSub[i][0] > minMemo)
      {
        minMemoNum++;
        nums[minMemoNum] = numsSub[i][1];
        minMemo = numsSub[i][0];
      }else
      {
        nums[minMemoNum] = Math.Min(nums[minMemoNum], numsSub[i][1]);
      }
    }
    
    rightMin[0] = nums[0];

    for(long i = 1; i < minMemoNum + 1; i++)
    {
      if(nums[i] > rightMin[answer-1])
      {
        rightMin[answer] = nums[i];
        answer++;
      }else
      {
        compareMemo = nums[i];
        rightMin[Search(0, answer-1)] = nums[i];//更新位置を二部探索する
      }
    }
    
		Console.WriteLine(answer);
	}

  static long Search(long min, long max)//二分探索法で最小値を求める
  {
    while (true)
    {
      long mid = min + (max - min) / 2;
      if(Check(mid)) max = mid;//さらに大きくても成り立つかも
      else min = mid;

      if(max - min <= 1)
      {
        if(Check(min)) 
        {
          return min;//最小値で成り立つかの確認を優先
        }
        else
        {
          return max;
        }
      break;
      }  
    }
  }

  static bool Check(long testNum)
  {
    if(rightMin[testNum] >= compareMemo) return true;//同じ数で右端を複数にしないように、等号を含む
    return false;
  }

}

Submission Info

Judge Result