結果
| 問題 | No.2930 Larger Mex |
| ユーザー |
 hirohiso
|
| 提出日時 | 2024-10-12 16:59:46 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,140 bytes |
| コンパイル時間 | 3,607 ms |
| コンパイル使用メモリ | 97,968 KB |
| 実行使用メモリ | 104,528 KB |
| 最終ジャッジ日時 | 2024-10-12 17:02:16 |
| 合計ジャッジ時間 | 75,477 ms |
|
ジャッジサーバーID （参考情報） |
judge / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | RE | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | RE | - |
| testcase_47 | RE | - |
| testcase_48 | RE | - |
| testcase_49 | RE | - |
| testcase_50 | WA | - |
| testcase_51 | WA | - |
| testcase_52 | WA | - |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.text.Format;
import java.util.*;
import java.util.function.BinaryOperator;
import java.util.function.Function;
import java.util.function.IntPredicate;
import java.util.function.Predicate;
import java.util.jar.JarEntry;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
@SuppressWarnings("unchecked")
public class Main {
public static void main(String[] args) {
solve(System.in, System.out);
}
private void solve(PrintWriter pw, FastScanner fs) {
var N = fs.ni();
var M = fs.ni();
var An = fs.nia(N);
var acc = new long[2 * N + 2];
var set = new TreeSet<Integer>();
for (int i = 0; i <= 200000; i++) {
set.add(i);
}
int j = 0;
for (int i = 0; i < N; i++) {
while (j < N) {
if (set.first() >= M) {
break;
}
set.remove(An[j]);
j++;
}
debug("i:j" + i + ":" + j);
debug(set.first());
if (set.first() >= M) {
debug(j - i);
acc[j - i]++;
acc[i + N - 1]--;
}
set.add(An[i]);
}
for (int i = 1; i < acc.length; i++) {
acc[i] += acc[i - 1];
}
debugArray(acc);
for (int i = 1; i < N; i++) {
pw.println(acc[i]);
}
}
record PSet(char c, int i) {
}
//--------------
record TPair<S, T>(S a, T b) {
}
record TTri<S, T, U>(S a, T b, U c) {
}
record Pair(long a, long b) {
}
record IntPair(int a, int b) {
}
record Triple(long a, long b, long c) {
}
public static int[] concat(int[] a, int[] b) {
var ret = new int[a.length + b.length];
for (int i = 0; i < a.length; i++) {
ret[i] = a[i];
}
for (int i = 0; i < b.length; i++) {
ret[i + a.length] = b[i];
}
return ret;
}
public static long[] concat(long[] a, long[] b) {
var ret = new long[a.length + b.length];
for (int i = 0; i < a.length; i++) {
ret[i] = a[i];
}
for (int i = 0; i < b.length; i++) {
ret[i + a.length] = b[i];
}
return ret;
}
public static void solve(InputStream in, PrintStream out) {
PrintWriter pw = new PrintWriter(out);
FastScanner fs = new FastScanner(in);
try {
new Main().solve(pw, fs);
} finally {
pw.flush();
}
}
//-------------------------------------------------------------------
private static void debug(Object x) {
System.err.println(x);
}
private static void debugArray(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
debugArray(arr[i]);
}
}
private static void debugArray(long[][] arr) {
for (int i = 0; i < arr.length; i++) {
debugArray(arr[i]);
}
}
private static void debugArray(int[] arr) {
debug(Arrays.toString(arr));
}
private static void debugArray(long[] arr) {
debug(Arrays.toString(arr));
}
private static void debugArray(boolean[] arr) {
debug(Arrays.toString(arr));
}
private static void debugArray(boolean[][] arr) {
for (int i = 0; i < arr.length; i++) {
debugArray(arr[i]);
}
}
/**
* 各インデックスが配列の長さ以内に収まっているか境界チェックを行う
* <p>
* 多次元配列のチェックをいちいち書くのがしんどい時に。
* arrayBound(new int[]{1,2,3} , new int[]{3,4,3})
*
* @param target 配列に設定したいインデックス
* @param len 配列の長さ
* @return 配列の長さ内に収まってる時 true
*/
private static boolean inarr(int[] target, int[] len) {
var b = true;
if (target.length != len.length) {
throw new IllegalArgumentException();
}
for (int i = 0; i < target.length; i++) {
b &= (0 <= target[i] && target[i] < len[i]);
}
return b;
}
private static int[] arr(int... a) {
return Arrays.copyOf(a, a.length);
}
private static long[] arr(long... a) {
return Arrays.copyOf(a, a.length);
}
//半時計90度回転
private static int[][] rot(int[][] grid) {
var h = grid.length;
var w = grid[0].length;
var result = new int[w][h];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
result[w - 1 - j][i] = grid[i][j];
}
}
return result;
}
//http://fantom1x.blog130.fc2.com/blog-entry-194.html
/**
* <h1>指定した値以上の先頭のインデクスを返す</h1>
* <p>配列要素が０のときは、０が返る。</p>
*
* @param arr ： 探索対象配列(単調増加であること)
* @param value ： 探索する値
* @return<b>int</b> ： 探索した値以上で、先頭になるインデクス
*/
public static final int lowerBound(final long[] arr, final long value) {
int low = 0;
int high = arr.length;
int mid;
while (low < high) {
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
if (arr[mid] < value) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
/**
* <h1>指定した値より大きい先頭のインデクスを返す</h1>
* <p>配列要素が０のときは、０が返る。</p>
*
* @param arr ： 探索対象配列(単調増加であること)
* @param value ： 探索する値
* @return<b>int</b> ： 探索した値より上で、先頭になるインデクス
*/
public static final int upperBound(final long[] arr, final long value) {
int low = 0;
int high = arr.length;
int mid;
while (low < high) {
mid = ((high - low) >>> 1) + low; //(low + high) / 2 (オーバーフロー対策)
if (arr[mid] <= value) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
//----------------
//-------------------------------------------------------------------
}
class FastScanner {
InputStream in;
byte[] buffer = new byte[1 << 10];
int length = 0;
int ptr = 0;
private final Predicate<Byte> isPrintable;
public FastScanner(InputStream in) {
this.in = in;
this.isPrintable = b -> (33 <= b && b <= 126);
}
public FastScanner(InputStream in, Predicate<Byte> predicate) {
this.in = in;
this.isPrintable = predicate;
}
private boolean hasNextByte() {
if (ptr < length) {
return true;
}
try {
length = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
ptr = 0;
return length != 0;
}
private byte read() {
if (hasNextByte()) {
return buffer[ptr++];
}
return 0;
}
private void skip() {
while (hasNextByte() && !isPrintable(buffer[ptr])) {
ptr++;
}
}
private boolean hasNext() {
skip();
return hasNextByte();
}
private boolean isPrintable(byte b) {
return 33 <= b && b <= 126;
}
private String innerNext(Predicate<Byte> isReadable) {
if (!hasNext()) {
throw new NoSuchElementException();
}
StringBuilder sb = new StringBuilder();
byte b = read();
while (isReadable.test(b)) {
sb.appendCodePoint(b);
b = read();
}
return sb.toString();
}
public String n() {
return innerNext(b -> (33 <= b && b <= 126));
}
public int ni() {
return (int) nl();
}
public char[][] ncaa(int n, int m) {
var grid = new char[n][m];
for (int i = 0; i < n; i++) {
grid[i] = n().toCharArray();
}
return grid;
}
public int[] nia(int n) {
int[] result = new int[n];
for (int i = 0; i < n; i++) {
result[i] = ni();
}
return result;
}
public int[][] niaa(int h, int w) {
int[][] result = new int[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
result[i][j] = ni();
}
}
return result;
}
public long[][] nlaa(int h, int w) {
long[][] result = new long[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
result[i][j] = nl();
}
}
return result;
}
public String[] na(int n) {
String[] result = new String[n];
for (int i = 0; i < n; i++) {
result[i] = n();
}
return result;
}
public long[] nla(int n) {
long[] result = new long[n];
for (int i = 0; i < n; i++) {
result[i] = nl();
}
return result;
}
public long nl() {
if (!hasNext()) {
throw new NoSuchElementException();
}
long result = 0;
boolean minus = false;
byte b;
b = read();
if (b == '-') {
minus = true;
b = read();
}
while (isPrintable(b)) {
if (b < '0' || b > '9') {
throw new NumberFormatException();
}
result *= 10;
result += (b - '0');
b = read();
}
return minus ? -result : result;
}
}