結果

問題 No.930 数列圧縮
ユーザー 👑 hos.lyric
提出日時 2019-11-22 22:06:11
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 97 ms / 2,000 ms
コード長 3,510 bytes
コンパイル時間 695 ms
コンパイル使用メモリ 125,912 KB
実行使用メモリ 10,264 KB
最終ジャッジ日時 2024-06-22 03:04:09
合計ジャッジ時間 3,363 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.numeric, std.regex, std.typecons;
import core.bitop;
class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens
    .popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }
bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }
int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1;
    (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }
enum INF = 10^^9;
void main() {
/*
debug {
foreach (n; 2 .. 6 + 1) {
auto as = iota(n).array;
do {
auto dp = new bool[1 << n];
dp[(1 << n) - 1] = true;
int[] sols;
foreach_reverse (p; 0 .. 1 << n) {
if (dp[p]) {
const js = iota(n).filter!(j => (p & 1 << j)).array;
if (js.length == 1) {
sols ~= js[0];
} else {
foreach (k; 1 .. js.length) {
if (as[js[k - 1]] < as[js[k]]) {
dp[p ^ 1 << js[k - 1]] = true;
dp[p ^ 1 << js[k]] = true;
}
}
}
}
}
writeln(as, ": ", sols);
assert((!sols.empty) == (as[0] < as[n - 1]));
} while (as.nextPermutation);
}
}
*/
try {
for (; ; ) {
const N = readInt();
auto A = new int[N];
foreach (i; 0 .. N) {
A[i] = readInt();
}
if (A[0] < A[N - 1]) {
auto lef = new int[N], rig = new int[N];
foreach (i; 0 .. N) {
lef[i] = i - 1;
rig[i] = i + 1;
}
int segN;
for (segN = 1; segN < N - 1; segN <<= 1) {}
alias Entry = Tuple!(int, "val", int, "pos");
auto seg = new Entry[segN << 1];
foreach (i; 0 .. N - 1) {
seg[segN + i] = Entry(A[i + 1] - A[i], i);
}
seg[segN + N - 1 .. $] = Entry(-INF, -1);
foreach_reverse (a; 1 .. segN) {
seg[a] = max(seg[a << 1], seg[a << 1 | 1]);
}
void segUpdate(int a, Entry e) {
seg[a += segN] = e;
for (; a >>= 1; ) {
seg[a] = max(seg[a << 1], seg[a << 1 | 1]);
}
}
int[] ans;
foreach (j; 0 .. N - 2) {
void remove(int i) {
ans ~= A[i];
segUpdate(lef[i], Entry(A[rig[i]] - A[lef[i]], lef[i]));
segUpdate(i, Entry(-INF, -1));
rig[lef[i]] = rig[i];
lef[rig[i]] = lef[i];
}
const i = seg[1].pos;
remove((i == 0) ? rig[i] : i);
}
writeln("Yes");
foreach (j; 0 .. N - 2) {
write(ans[j], " ");
}
writeln(A[0]);
} else {
writeln("No");
}
}
} catch (EOFException e) {
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0