結果

問題 No.871 かえるのうた
ユーザー itt828itt828
提出日時 2020-04-23 09:19:39
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 6,409 bytes
コンパイル時間 1,000 ms
コンパイル使用メモリ 118,664 KB
実行使用メモリ 54,940 KB
最終ジャッジ日時 2024-10-13 06:11:19
合計ジャッジ時間 5,870 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
19,200 KB
testcase_01 WA -
testcase_02 AC 30 ms
19,200 KB
testcase_03 AC 31 ms
18,944 KB
testcase_04 WA -
testcase_05 AC 30 ms
19,072 KB
testcase_06 WA -
testcase_07 AC 30 ms
19,072 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 35 ms
19,584 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 136 ms
41,216 KB
testcase_15 WA -
testcase_16 AC 141 ms
41,216 KB
testcase_17 AC 126 ms
42,240 KB
testcase_18 AC 49 ms
22,784 KB
testcase_19 WA -
testcase_20 AC 42 ms
21,372 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 AC 31 ms
18,944 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 30 ms
19,072 KB
testcase_29 AC 78 ms
32,640 KB
testcase_30 WA -
testcase_31 AC 37 ms
19,840 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 AC 53 ms
23,808 KB
testcase_35 WA -
testcase_36 AC 101 ms
38,144 KB
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 AC 95 ms
32,000 KB
testcase_41 AC 31 ms
19,200 KB
testcase_42 AC 68 ms
27,648 KB
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 AC 32 ms
18,944 KB
testcase_47 AC 31 ms
19,072 KB
testcase_48 AC 31 ms
19,200 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using System.Numerics;
using System.IO;
using System.Runtime.InteropServices;
using static System.Math;
using static Math2;
using static io;
using static Utils;

public class CompetitiveProgramming
{
  public void Solve()
  {
    var T = 1;
    while (T > 0)
    {
      --T;
      tcase();
    }


  }
  public void tcase()
  {
    var (N, K) = Cin<int, int>();
    --K;
    var X = Longs;
    var A = Longs;
    int r = K;
    int l = K;
    while (true)
    {
      int pr = r;
      r = BinarySearch.Upper_Bound(X, X[r] + A[r]);
      --r;
      if (pr == r) break;
      if (r >= N - 1)
      {
        r = N - 1;
        break;
      }
    }
    while (true)
    {
      int pl = l;
      l = BinarySearch.Lower_Bound(X, X[l] - A[l]);
      if (pl == l) break;
      if (l < 0)
      {
        l = 0;
        break;
      }
    }
    Write(r - l + 1);

  }
}
public class BinarySearch
{
  public static int Lower_Bound<T>(T[] Array, T Target) => Lower_Bound(Array, Target, Comparer<T>.Default.Compare);
  public static int Lower_Bound<T>(T[] Array, T Target, Comparison<T> Comp)
  {
    var cmp = Comparer<T>.Create(Comp);
    var l = -1; //always ng
    var r = Array.Length; //always ok
    if (cmp.Compare(Array[0], Target) > 0) return -1;
    while (r - l > 1)
    {
      var mid = l + (r - l) / 2;
      var res = cmp.Compare(Array[mid], Target);
      if (res >= 0) r = mid;
      else l = mid;
    }
    return r;
  }
  public static int Upper_Bound<T>(T[] Array, T Target) => Upper_Bound(Array, Target, Comparer<T>.Default.Compare);
  public static int Upper_Bound<T>(T[] Array, T Target, Comparison<T> Comp)
  {
    var cmp = Comparer<T>.Create(Comp);
    var l = -1;
    var r = Array.Length;
    if (cmp.Compare(Array[0], Target) >= 0) return -1;
    while (r - l > 1)
    {
      var mid = l + (r - l) / 2;
      var res = cmp.Compare(Array[mid], Target);
      if (res > 0) r = mid;
      else l = mid;
    }
    return r;
  }
}


public static class Math2
{
  public const int INF = 1 << 29;
  public const long INFL = 1L << 60;
  public const int MOD = 1000000007;
  public const int MOD2 = 998244353;

  public static long Pow(long i, long N, long MOD = 1000000007)
  {
    long res = 1;
    while (N > 0)
    {
      if ((N & 1) != 0) res = res * i % MOD;
      i = i * i % MOD;
      N >>= 1;
    }
    return res;
  }
  public static long GCD(long i, long N)
  {
    if (i > N) Swap(ref i, ref N);
    if (i == 0) return N;
    while (N != 0)
    {
      var r = i % N;
      i = N;
      N = r;
    }
    return i;
  }
  public static long LCM(long i, long N) => i * N / GCD(i, N);
  public static long Comb(long N, long R, int MOD = 1000000007)
  {
    long ret = 1;
    long x = 1;
    for (long i = N; i >= N - R + 1; --i)
    {
      ret = ret / x * i;
      ret %= MOD;
      x++;
    }
    return ret;
  }
  public static long Comb2(long N, long R)
  {
    long Nume = 1;
    long Deno = 1;

    if (R > N - R) Swap(ref N, ref R);
    for (long i = 1; i <= R; ++i)
    {
      Deno *= i;
      Nume *= N - i + 1;
    }
    return Deno / Nume;
  }

}
public static class Utils
{
  public static void Swap<T>(ref T A, ref T B)
  {
    T x = A;
    A = B;
    B = x;
  }
  public static int DigitSum(string N)
  {

    int ret = 0;
    for (int i = 0; i < N.Length; ++i) ret += N[i] - '0';
    return ret;
  }
}
class Program
{
  static void Main(string[] args)
  {
    var CompetitiveProgramming = new CompetitiveProgramming();
    CompetitiveProgramming.Solve();
  }
}
public static class io
{
  public static string Str => Console.ReadLine();
  public static string[] Strs => Str.Split(' ');
  public static long[] Longs => Strs.Select(long.Parse).ToArray();
  public static int[] Ints => Strs.Select(int.Parse).ToArray();
  public static char[] Chars => Str.ToArray();
  public static double[] Doubles => Strs.Select(double.Parse).ToArray();
  public static long Long1 => Longs[0];
  public static int Int1 => Ints[0];
  public static char Char1 => Chars[0];
  public static double Double1 => Doubles[0];
  public static long[] VerticalRead(int N) { long[] A = new long[N]; for (int i = 0; i < N; ++i) A[i] = Long1; return A; }
  public static void Write(string a) => Console.WriteLine(a);
  public static void Write(params object[] i) => Write(string.Join(" ", i));
  public static void Write<T>(IEnumerable<T> a) => Write(string.Join(" ", a));
  public static void Verticalwrite<T>(IEnumerable<T> a) { foreach (var z in a) Write(z); }
  public static void YN(bool i) { if (i) Write("Yes"); else Write("No"); }


  public static bool IsTypeEqual<T, U>() => typeof(T).Equals(typeof(U));
  public static T ConvertType<T, U>(U a) => (T)Convert.ChangeType(a, typeof(T));
  public static T Cast<T>(string s)
  {
    if (IsTypeEqual<T, int>()) return ConvertType<T, int>(int.Parse(s));
    else if (IsTypeEqual<T, long>()) return ConvertType<T, long>(long.Parse(s));
    else if (IsTypeEqual<T, double>()) return ConvertType<T, double>(double.Parse(s));
    else if (IsTypeEqual<T, char>()) return ConvertType<T, char>(char.Parse(s));
    else return ConvertType<T, string>(s);
  }
  public static (T, U) Cin<T, U>() { var t = Strs; return (Cast<T>(t[0]), Cast<U>(t[1])); }
  public static (T, U, V) Cin<T, U, V>() { var t = Strs; return (Cast<T>(t[0]), Cast<U>(t[1]), Cast<V>(t[2])); }
  public static (T, U, V, W) Cin<T, U, V, W>() { var t = Strs; return (Cast<T>(t[0]), Cast<U>(t[1]), Cast<V>(t[2]), Cast<W>(t[3])); }
  public static (T, U, V, W, X) Cin<T, U, V, W, X>() { var t = Strs; return (Cast<T>(t[0]), Cast<U>(t[1]), Cast<V>(t[2]), Cast<W>(t[3]), Cast<X>(t[4])); }
  public static (T, U, V, W, X, Y) Cin<T, U, V, W, X, Y>() { var t = Strs; return (Cast<T>(t[0]), Cast<U>(t[1]), Cast<V>(t[2]), Cast<W>(t[3]), Cast<X>(t[4]), Cast<Y>(t[5])); }
  public static (T, U, V, W, X, Y, Z) Cin<T, U, V, W, X, Y, Z>() { var t = Strs; return (Cast<T>(t[0]), Cast<U>(t[1]), Cast<V>(t[2]), Cast<W>(t[3]), Cast<X>(t[4]), Cast<Y>(t[5]), Cast<Z>(t[6])); }
}
0