Submission #3452584


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]);
    }
    var sorted = numsSub.OrderBy(a => a[0]).ThenByDescending(a => a[1]).ToList();
    
    for(long i = 0; i < n; i++)
    {
      nums[i] = sorted[(int)i][1];
    }
    
    rightMin[0] = nums[0];

    for(long i = 1; i < n; 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(nums[0]+" "+nums[1]+" "+nums[2]+" "+nums[3]+" "+nums[4]+" ");
		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

Submission Time
Task D - プレゼント
User suikameron
Language C# (Mono 4.6.2.0)
Score 100
Code Size 1947 Byte
Status AC
Exec Time 204 ms
Memory 31172 KB

Judge Result

Set Name Sample Subtask0 All
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 4
AC × 19
AC × 34
Set Name Test Cases
Sample sample0.txt, sample1.txt, sample2.txt, sample3.txt
Subtask0 subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, sample0.txt, sample1.txt, sample2.txt, sample3.txt
All sample0.txt, sample1.txt, sample2.txt, sample3.txt, subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
sample0.txt AC 26 ms 13524 KB
sample1.txt AC 25 ms 11348 KB
sample2.txt AC 26 ms 13396 KB
sample3.txt AC 26 ms 11348 KB
subtask0_0.txt AC 27 ms 13524 KB
subtask0_1.txt AC 26 ms 11476 KB
subtask0_10.txt AC 27 ms 11476 KB
subtask0_11.txt AC 27 ms 11476 KB
subtask0_12.txt AC 27 ms 11476 KB
subtask0_13.txt AC 27 ms 9428 KB
subtask0_14.txt AC 27 ms 11476 KB
subtask0_2.txt AC 25 ms 11476 KB
subtask0_3.txt AC 25 ms 11476 KB
subtask0_4.txt AC 27 ms 13504 KB
subtask0_5.txt AC 26 ms 11476 KB
subtask0_6.txt AC 27 ms 11456 KB
subtask0_7.txt AC 27 ms 13504 KB
subtask0_8.txt AC 26 ms 9408 KB
subtask0_9.txt AC 25 ms 9428 KB
subtask1_0.txt AC 129 ms 26448 KB
subtask1_1.txt AC 28 ms 11604 KB
subtask1_10.txt AC 150 ms 31172 KB
subtask1_11.txt AC 151 ms 27076 KB
subtask1_12.txt AC 200 ms 29124 KB
subtask1_13.txt AC 204 ms 27076 KB
subtask1_14.txt AC 196 ms 27076 KB
subtask1_2.txt AC 53 ms 19292 KB
subtask1_3.txt AC 170 ms 25416 KB
subtask1_4.txt AC 197 ms 24900 KB
subtask1_5.txt AC 49 ms 17116 KB
subtask1_6.txt AC 152 ms 22220 KB
subtask1_7.txt AC 92 ms 20308 KB
subtask1_8.txt AC 175 ms 29768 KB
subtask1_9.txt AC 100 ms 22868 KB