結果
| 問題 |
No.1341 真ん中を入れ替えて門松列
|
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2019-12-15 18:02:51 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 474 ms / 2,000 ms |
| コード長 | 6,849 bytes |
| コンパイル時間 | 2,672 ms |
| コンパイル使用メモリ | 82,636 KB |
| 実行使用メモリ | 49,084 KB |
| 最終ジャッジ日時 | 2024-09-21 11:58:51 |
| 合計ジャッジ時間 | 7,826 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 14 |
ソースコード
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);
}
final void run() {
Scanner sc = new Scanner();
int N = sc.nextInt();
long M = sc.nextLong();
long[][] A = new long[N][2];
long[] C = new long[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, C);
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, long[] C, boolean center) {
if(!pq.isEmpty())
{
throw new AssertionError();
}
for (int i = 0; i < N; ++i) {
long l = binarySearchLeft(A[i][0], C);
long r = binarySearchRight(A[i][1], C);
if (!center) {
l = Math.min(l, middle);
r = Math.max(r, middle + 1);
}
A[i] = new long[] { l, r, 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 -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 -1;
}
for (int i = N - 1; i >= pq.size(); --i) {
ans += C[i];
}
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)
A[i][j] = A_[i][j];
return A;
}
int[] need;
int[] sz;
long[][] A;
final String[] solve(int N, long M, long[][] A_, long[] C) {
need = new int[N];
sz = new int[N];
A = new long[A_.length][A_[0].length];
for (int i = 0; i < A_.length; ++i)
Arrays.sort(A_[i]);
Arrays.sort(C);
long ret = -1;
long center = check(-1, N, M, copy(A_), C, true);
if (center == -1)
return new String[] { "NO" };
long left, right;
if (check(-1, N, M, copy(A_), C, false) > 0) {
left = -1;
} else {
long lng = -1;
left = center;
while (left - lng > 1) {
long middle = (left + lng) / 2;
if (check(middle, N, M, copy(A_), C, false) > 0) {
left = middle;
} else {
lng = middle;
}
}
}
if (check(N, N, M, copy(A_), C, false) > 0) {
right = N;
} else {
long rng = N;
right = center;
while (rng - right > 1) {
long middle = (rng + right) / 2;
if (check(middle, N, M, copy(A_), C, false) > 0) {
right = middle;
} else {
rng = middle;
}
}
}
while (right - left > 2) {
long lm = (right + 2 * left) / 3;// l+(r-l)/3=(r+2l)/3
long rm = (2 * right + left) / 3;
long lmv = check(lm, N, M, copy(A_), C, false);
long rmv = check(rm, N, M, copy(A_), C, 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_), C, false));
if (ret >= M)
return new String[] { "YES", "KADOMATSU!" };
else if (ret > 0) {
return new String[] { "YES", "NO" };
} else {
return new String[] { "NO" };
}
}
HashMap<Long, Integer> right = new HashMap<>();
final int binarySearchRight(long key, long[] a) {
if (right.containsKey(key))
return right.get(key);
int ok = a.length;
int ng = -1;
while (ok - ng > 1) {
int middle = (ok + ng) / 2;
if (a[middle] > key) {
ok = middle;
} else {
ng = middle;
}
}
right.put(key, ok);
return ok;
}
HashMap<Long, Integer> left = new HashMap<>();
final int binarySearchLeft(long key, long[] a) {
if (left.containsKey(key))
return left.get(key);
int ok = -1;
int ng = a.length;
while (ng - ok > 1) {
int middle = (ok + ng) / 2;
if (a[middle] < key) {
ok = middle;
} else {
ng = middle;
}
}
left.put(key, ok);
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();
}
}
}