結果
| 問題 | No.1095 Smallest Kadomatsu Subsequence |
| ユーザー |
 ywmt
|
| 提出日時 | 2020-06-26 21:39:16 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 695 ms / 2,000 ms |
| コード長 | 6,110 bytes |
| コンパイル時間 | 2,608 ms |
| コンパイル使用メモリ | 90,076 KB |
| 実行使用メモリ | 139,892 KB |
| 最終ジャッジ日時 | 2024-07-04 20:10:06 |
| 合計ジャッジ時間 | 12,006 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 30 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.util.function.BinaryOperator;
public class Main {
static PrintWriter out;
static InputReader ir;
static void solve() {
int n = ir.nextInt();
long[] a = ir.nextLongArray(n);
BinaryOperator<Long> fmi = (A, B) -> Math.min(A, B);
DisjointSparseTable dismi = new DisjointSparseTable(fmi, a);
BinaryOperator<Long> fma = (A, B) -> Math.max(A, B);
DisjointSparseTable disma = new DisjointSparseTable(fma, a);
long mi = 1L << 60;
for (int i = 1; i < n - 1; i++) {
long l = dismi.query(0, i);
long r = dismi.query(i + 1, n);
if (a[i] > l && a[i] > r) {
mi = Math.min(l + r + a[i], mi);
}
if (a[i] < l && a[i] < r) {
mi = Math.min(l + r + a[i], mi);
}
l = disma.query(0, i);
r = disma.query(i + 1, n);
if (a[i] > l && a[i] > r) {
mi = Math.min(l + r + a[i], mi);
}
if (a[i] < l && a[i] < r) {
mi = Math.min(l + r + a[i], mi);
}
}
out.println(mi == 1L << 60 ? -1 : mi);
}
static class DisjointSparseTable {
BinaryOperator<Long> f;
long[][] dat;
long[] ht;
DisjointSparseTable(BinaryOperator<Long> f, long[] v) {
this.f = f;
int n = v.length, h = 1;
while ((1 << h) <= n)
h++;
dat = new long[h][n];
ht = new long[(1 << h) + 1];
for (int j = 2; j < (1 << h) + 1; j++)
ht[j] = ht[j >> 1] + 1;
for (int j = 0; j < n; j++)
dat[0][j] = v[j];
for (int i = 1; i < h; i++) {
int s = 1 << i;
for (int j = 0; j < n; j += s << 1) {
int t = Math.min(j + s, n);
dat[i][t - 1] = v[t - 1];
for (int k = t - 2; k >= j; k--)
dat[i][k] = f.apply(v[k], dat[i][k + 1]);
if (n <= t)
break;
dat[i][t] = v[t];
int r = Math.min(t + s, n);
for (int k = t + 1; k < r; k++)
dat[i][k] = f.apply(dat[i][k - 1], v[k]);
}
}
}
// [l,r)
public long query(int l, int r) {
if (l >= --r)
return dat[0][l];
return f.apply(dat[(int) ht[l ^ r]][l], dat[(int) ht[l ^ r]][r]);
}
public int length() {
return dat[0].length;
}
}
static class SegmentTree {
BinaryOperator<Long> f;
int n;
long[] seg;
long e;
public SegmentTree(int nn, BinaryOperator<Long> f, long e) {
this.f = f;
this.e = e;
n = 1;
while (n < nn)
n <<= 1;
seg = new long[n * 2 - 1];
Arrays.fill(seg, e);
}
public SegmentTree(long[] a, BinaryOperator<Long> f, long e) {
this.f = f;
this.e = e;
n = 1;
while (n < a.length)
n <<= 1;
seg = new long[n * 2 - 1];
Arrays.fill(seg, e);
for (int i = 0; i < a.length; i++)
seg[i + n - 1] = a[i];
for (int i = n - 2; i >= 0; i--)
seg[i] = f.apply(seg[i * 2 + 1], seg[i * 2 + 2]);
}
public long query(int l, int r) {
return query(l, r, 0, 0, n);
}
private long query(int a, int b, int k, int l, int r) {
if (a <= l && r <= b)
return seg[k];
if (r <= a || b <= l)
return e;
long vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
long vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
return f.apply(vl, vr);
}
void update(int i, int x) {
i += n - 1;
seg[i] = x;
while (i > 0) {
i = (i - 1) / 2;
seg[i] = f.apply(seg[i * 2 + 1], seg[i * 2 + 2]);
}
}
}
public static void main(String[] args) {
ir = new InputReader(System.in);
out = new PrintWriter(System.out);
solve();
out.flush();
}
static class InputReader {
private InputStream in;
private byte[] buffer = new byte[1024];
private int curbuf;
private int lenbuf;
public InputReader(InputStream in) {
this.in = in;
this.curbuf = this.lenbuf = 0;
}
public boolean hasNextByte() {
if (curbuf >= lenbuf) {
curbuf = 0;
try {
lenbuf = in.read(buffer);
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return false;
}
return true;
}
private int readByte() {
if (hasNextByte())
return buffer[curbuf++];
else
return -1;
}
private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}
private void skip() {
while (hasNextByte() && isSpaceChar(buffer[curbuf]))
curbuf++;
}
public boolean hasNext() {
skip();
return hasNextByte();
}
public String next() {
if (!hasNext())
throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (!isSpaceChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public int nextInt() {
if (!hasNext())
throw new NoSuchElementException();
int c = readByte();
while (isSpaceChar(c))
c = readByte();
boolean minus = false;
if (c == '-') {
minus = true;
c = readByte();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res = res * 10 + c - '0';
c = readByte();
} while (!isSpaceChar(c));
return (minus) ? -res : res;
}
public long nextLong() {
if (!hasNext())
throw new NoSuchElementException();
int c = readByte();
while (isSpaceChar(c))
c = readByte();
boolean minus = false;
if (c == '-') {
minus = true;
c = readByte();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res = res * 10 + c - '0';
c = readByte();
} while (!isSpaceChar(c));
return (minus) ? -res : res;
}
public double nextDouble() {
return Double.parseDouble(next());
}
public int[] nextIntArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
public long[] nextLongArray(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nextLong();
return a;
}
public char[][] nextCharMap(int n, int m) {
char[][] map = new char[n][m];
for (int i = 0; i < n; i++)
map[i] = next().toCharArray();
return map;
}
}
static void tr(Object... o) {
System.err.println(Arrays.deepToString(o));
}
}