結果
| 問題 |
No.1341 真ん中を入れ替えて門松列
|
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2019-12-26 09:27:05 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,352 bytes |
| コンパイル時間 | 3,089 ms |
| コンパイル使用メモリ | 89,948 KB |
| 実行使用メモリ | 50,068 KB |
| 最終ジャッジ日時 | 2024-09-21 12:00:58 |
| 合計ジャッジ時間 | 7,010 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 13 WA * 1 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
class Main {
public static void main(String[] args) {
long curtime = System.currentTimeMillis();
new Main().run();
System.err.println(System.currentTimeMillis() - curtime);
}
long[] C;
long[] sumC;
int[] l;
int[] r;
final void run() {
Scanner sc = new Scanner();
int N = sc.nextInt();
long M = sc.nextLong();
long[][] A = new long[N][2];
C = new long[N];
sumC = new long[N];
l = new int[N];
r = new int[N];
for (int i = 0; i < N; ++i) {
A[i][0] = sc.nextInt();
C[i] = sc.nextInt();
A[i][1] = sc.nextInt();
}
String[] ret = solve(N, M, A);
for (String s : ret) {
System.out.println(s);
}
}
PriorityQueue<long[]> pq = new PriorityQueue<>(new Comparator<long[]>() {
@Override
public int compare(long[] o1, long[] o2) {
if (o1[0] != o2[0])
return Long.compare(o1[0], o2[0]);
else
return Long.compare(o1[2], o2[2]);
}
});
final long check(long middle, int N, long M, long[][] A, boolean center) {
if (!pq.isEmpty()) {
throw new AssertionError();
}
for (int i = 0; i < N; ++i) {
long l_after = l[i];
binarySearchLeft(A[i][0]);
long r_after = r[i];
binarySearchRight(A[i][1]);
if (!center) {
l_after = Math.min(l_after, middle);
r_after = Math.max(r_after, middle + 1);
}
A[i] = new long[] { l_after, r_after, A[i][0], A[i][1] };
}
Arrays.sort(A, new Comparator<long[]>() {
@Override
public int compare(long[] o1, long[] o2) {
return Long.compare(o1[0], o2[0]);
}
});
int p = 0, maxsz = 0;
long ans = 0;
Arrays.fill(need, 0);
Arrays.fill(sz, 0);
for (int i = -1; i <= N; ++i) {
while (p < A.length && A[p][0] <= i) {
pq.add(new long[] { A[p][1], A[p][2], A[p][3] });
++p;
maxsz = Math.max(maxsz, pq.size());
}
while (pq.size() > i + 1) {
long[] v = pq.poll();
if (v[0] >= N) {
pq.clear();
return -Math.min(middle+1,N+1-middle)-1;
}
need[(int) v[0]]--;
}
if (0 <= i && i < sz.length)
sz[i] = pq.size();
}
for (int i = 1; i < N; ++i) {
need[i] = need[i - 1] + need[i];
}
boolean ok = true;
int pnd = 0, cur = 0;
for (int i = 0; i < N; ++i) {
pnd += Math.abs(need[i]);
if (pnd > 0) {
++cur;
--pnd;
}
need[i] = (i + 1) - cur;
}
int max = 0;
for (int i = N - 1; i >= 0; --i) {
max = Math.max(max, sz[i]);
ok &= max >= need[i];
}
if (!ok) {
pq.clear();
return -Math.min(middle+1,N+1-middle)-1;
}
ans += sumC[N - 1] - (pq.size() > 0 ? sumC[pq.size() - 1] : 0);
if (center) {
int ret = pq.size();
pq.clear();
return ret;
}
while (!pq.isEmpty()) {
ans += pq.poll()[2];
}
return ans;
}
final long[][] copy(long[][] A_) {
for (int i = 0; i < A_.length; ++i)
for (int j = 0; j < A_[i].length; ++j)
tmpA[i][j] = A_[i][j];
return tmpA;
}
int[] need;
int[] sz;
long[][] tmpA;
final String[] solve(int N, long M, long[][] A_) {
need = new int[N];
sz = new int[N];
tmpA = new long[A_.length][A_[0].length];
for (int i = 0; i < A_.length; ++i)
Arrays.sort(A_[i]);
Arrays.sort(C);
for (int i = 0; i < sumC.length; ++i)
sumC[i] = (i > 0 ? sumC[i - 1] : 0) + C[i];
{
for (int i = 0; i < N; ++i) {
l[i] = binarySearchLeft(A_[i][0]);
r[i] = binarySearchRight(A_[i][1]);
}
}
long ret = -Long.MAX_VALUE/3;
long right=N;
long left=-1;
double gr=(Math.sqrt(5)+1)/2;
while (right - left > 2) {
long lm = (long)(right - (right - left) / gr);
long rm = (long)(left + (right - left) / gr);
long lmv = check(lm, N, M, copy(A_), false);
long rmv = check(rm, N, M, copy(A_), false);
if (lmv > rmv)
right = rm;
else
left = lm;
ret = Math.max(ret, lmv);
ret = Math.max(ret, rmv);
}
for (long i = left; i <= right; ++i)
ret = Math.max(ret, check(i, N, M, copy(A_), false));
if (ret >= M)
return new String[] { "YES", "KADOMATSU!" };
else if (ret > 0) {
return new String[] { "YES", "NO" };
} else {
return new String[] { "NO" };
}
}
final int binarySearchRight(long key) {
int ok = C.length;
int ng = -1;
while (ok - ng > 1) {
int middle = (ok + ng) / 2;
if (C[middle] > key) {
ok = middle;
} else {
ng = middle;
}
}
return ok;
}
final int binarySearchLeft(long key) {
int ok = -1;
int ng = C.length;
while (ng - ok > 1) {
int middle = (ok + ng) / 2;
if (C[middle] < key) {
ok = middle;
} else {
ng = middle;
}
}
return ok;
}
void tr(Object... objects) {
System.out.println(Arrays.deepToString(objects));
}
}
class Scanner {
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte())
return buffer[ptr++];
else
return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private void skipUnprintable() {
while (hasNextByte() && !isPrintableChar(buffer[ptr]))
ptr++;
}
public boolean hasNext() {
skipUnprintable();
return hasNextByte();
}
public String next() {
if (!hasNext())
throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public int nextInt() {
return (int) nextLong();
}
public long nextLong() {
if (!hasNext())
throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) {
return minus ? -n : n;
} else {
throw new NumberFormatException();
}
b = readByte();
}
}
}