Submission #4362828

Source Code Expand

Copy
```import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.TreeSet;

public class Main {

public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
MyInput in = new MyInput(inputStream);
PrintWriter out = new PrintWriter(outputStream);
solver.solve(1, in, out);
out.close();
}

static int INF = 1 << 30;
static long LINF = 1L << 55;
static int MOD = 1000000007;
static int[] mh4 = { 0, -1, 1, 0 };
static int[] mw4 = { -1, 0, 0, 1 };
static int[] mh8 = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int[] mw8 = { -1, 0, 1, -1, 1, -1, 0, 1 };

public void solve(int testNumber, MyInput in, PrintWriter out) {

int n = in.nextInt();
int[] a = in.nextIntArray1Index(n);
int[] idx = new int[n+2];
for (int i = 1; i < n+1; i++) {
idx[a[i]] = i;
}

TreeSet<Integer> set = new TreeSet<>();

long ans = 0;
for (int i = 1; i <= n; i++) {
long l = idx[i] - set.lower(idx[i]);
long r = set.higher(idx[i]) - idx[i];
ans += r * l * i;
}

out.println(ans);
}
}

static void printArrayLine(int[] a, PrintWriter out) {
int n = a.length;
for (int i = 0; i < n; i++) {
if (i == 0) {
out.print(a[i]);
} else {
out.print(" " + a[i]);
}
}
out.print("\n");
}

static class MyInput {
private static int pos;
private static final char[] buffer = new char[1024 * 8];
private static char[] str = new char[500 * 8 * 2];
private static boolean[] isDigit = new boolean[256];
private static boolean[] isSpace = new boolean[256];
private static boolean[] isLineSep = new boolean[256];

static {
for (int i = 0; i < 10; i++) {
isDigit['0' + i] = true;
}
isDigit['-'] = true;
isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;
isLineSep['\r'] = isLineSep['\n'] = true;
}

public MyInput(InputStream is) {
}

pos = 0;
try {
} catch (IOException e) {
throw new RuntimeException();
}
throw new MyInput.EndOfFileRuntimeException();
}
}
return buffer[pos++];
}

public int nextInt() {
int len = 0;
str[len++] = nextChar();
int i = 0;
int ret = 0;
if (str[0] == '-') {
i = 1;
}
for (; i < len; i++)
ret = ret * 10 + str[i] - '0';
if (str[0] == '-') {
ret = -ret;
}
return ret;
}

public long nextLong() {
int len = 0;
str[len++] = nextChar();
int i = 0;
long ret = 0;
if (str[0] == '-') {
i = 1;
}
for (; i < len; i++)
ret = ret * 10 + str[i] - '0';
if (str[0] == '-') {
ret = -ret;
}
return ret;
}

public char nextChar() {
while (true) {
if (!isSpace[c]) {
return (char) c;
}
}
}

public String nextString() {
return new String(nextChars());
}

public char[] nextChars() {
int len = 0;
str[len++] = nextChar();
return Arrays.copyOf(str, len);
}

public char[][] next2DChars(int h, int w) {
char[][] s = new char[h][w];
for (int i = 0; i < h; i++) {
s[i] = nextChars();
}
return s;
}

int reads(int len, boolean[] accept) {
try {
while (true) {
if (accept[c]) {
break;
}
if (str.length == len) {
char[] rep = new char[str.length * 3 / 2];
System.arraycopy(str, 0, rep, 0, str.length);
str = rep;
}
str[len++] = (char) c;
}
} catch (MyInput.EndOfFileRuntimeException e) {
}
return len;
}

public int[] nextIntArray(final int n) {
final int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt();
}
return res;
}

public int[] nextIntArray1Index(final int n) {
final int[] res = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
res[i] = nextInt();
}
return res;
}

public int[] nextIntArrayDec(final int n) {
final int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt() - 1;
}
return res;
}

public long[] nextLongArray(final int n) {
final long[] res = new long[n];
for (int i = 0; i < n; i++) {
res[i] = nextLong();
}
return res;
}

public long[] nextLongArray1Index(final int n) {
final long[] res = new long[n + 1];
for (int i = 1; i < n + 1; i++) {
res[i] = nextLong();
}
return res;
}

public long[] nextLongArrayDec(final int n) {
final long[] res = new long[n];
for (int i = 0; i < n; i++) {
res[i] = nextLong() - 1;
}
return res;
}

public double nextDouble() {
return Double.parseDouble(nextString());
}

public double[] nextDoubleArray(int n) {
double[] res = new double[n];
for (int i = 0; i < n; i++) {
res[i] = nextDouble();
}
return res;
}

static class EndOfFileRuntimeException extends RuntimeException {
}

}

}
```

#### Submission Info

Submission Time 2019-02-24 12:48:07+0900 B - Minimum Sum tutuz Java8 (OpenJDK 1.8.0) 400 5636 Byte AC 353 ms 50792 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0, example1, example2
All 400 / 400 corner0, corner1, corner2, corner3, example0, example1, example2, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2
Case Name Status Exec Time Memory
corner0 295 ms 47880 KB
corner1 277 ms 36164 KB
corner2 76 ms 19028 KB
corner3 315 ms 50340 KB
example0 75 ms 18900 KB
example1 74 ms 21460 KB
example2 75 ms 19668 KB
maxrand0 327 ms 49964 KB
maxrand1 353 ms 50792 KB
maxrand2 331 ms 48316 KB
rand0 79 ms 19028 KB
rand1 76 ms 18516 KB
rand2 77 ms 21204 KB