結果

問題 No.871 かえるのうた
コンテスト
ユーザー ks2m
提出日時 2019-08-30 21:49:52
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,135 ms / 2,000 ms
コード長 1,303 bytes
コンパイル時間 2,226 ms
コンパイル使用メモリ 78,176 KB
実行使用メモリ 144,032 KB
最終ジャッジ日時 2024-11-30 10:46:23
合計ジャッジ時間 11,840 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int k = Integer.parseInt(sa[1]) - 1;
		sa = br.readLine().split(" ");
		long[] x = new long[n];
		for (int i = 0; i < n; i++) {
			x[i] = Long.parseLong(sa[i]);
		}
		sa = br.readLine().split(" ");
		long[] a = new long[n];
		for (int i = 0; i < n; i++) {
			a[i] = Long.parseLong(sa[i]);
		}
		br.close();

		Queue<Integer> que = new ArrayDeque<>();
		que.add(k);
		boolean[] flg = new boolean[n];
		flg[k] = true;
		long min = x[k];
		long max = x[k];
		while (!que.isEmpty()) {
			int cur = que.poll();
			long l = x[cur] - a[cur];
			if (l < min) {
				min = l;
				for (int i = cur - 1; i >= 0 && l <= x[i]; i--) {
					flg[i] = true;
					que.add(i);
				}
			}
			long r = x[cur] + a[cur];
			if (max < r) {
				max = r;
				for (int i = cur + 1; i < n && x[i] <= r; i++) {
					flg[i] = true;
					que.add(i);
				}
			}
		}

		int ans = 0;
		for (int i = 0; i < n; i++) {
			if (flg[i]) {
				ans++;
			}
		}
		System.out.println(ans);
	}
}
0