結果
| 問題 |
No.742 にゃんにゃんにゃん 猫の挨拶
|
| コンテスト | |
| ユーザー |
 Grenache
|
| 提出日時 | 2019-05-05 20:35:48 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 159 ms / 2,500 ms |
| コード長 | 6,201 bytes |
| コンパイル時間 | 5,372 ms |
| コンパイル使用メモリ | 92,152 KB |
| 実行使用メモリ | 55,104 KB |
| 最終ジャッジ日時 | 2024-06-26 00:14:20 |
| 合計ジャッジ時間 | 7,540 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 16 |
ソースコード
import java.io.*;
import java.util.*;
public class Main_yukicoder742 {
private static Scanner sc;
private static Printer pr;
private static void solve() {
int n = sc.nextInt();
int[] m = new int[n];
List<Integer> rl = new ArrayList<>();
List<Integer> ll = new ArrayList<>();
for (int i = 0; i < n; i++) {
m[i] = sc.nextInt() - 1;
if (m[i] >= i) {
rl.add(i);
} else {
ll.add(i);
}
}
// 右端の逆順
Collections.sort(ll, (o1, o2) -> {
if (o1 == o2) {
Integer.compare(m[o2], m[o1]);
}
return Integer.compare(o2, o1);
});
// pr.println(rl);
// pr.println(ll);
long ans = 0;
RSQ rsqr = new RSQ(n);
for (int i : rl) {
ans += rsqr.query(m[i], n);
rsqr.add(m[i], 1);
}
RSQ rsql = new RSQ(n);
for (int j : ll) {
ans += rsql.query(0, m[j]);
rsql.add(m[j], 1);
}
// pr.println(ans);
// 右端の正順
Collections.reverse(ll);
RSQ rsq = new RSQ(n);
int i = 0, size = rl.size();
for (int j : ll) {
while (i < size && rl.get(i) <= j) {
rsq.add(m[rl.get(i++)], 1);
}
ans += rsq.query(m[j], n);
}
pr.println(ans);
}
// Range Sum Query by Segment Tree
static class RSQ {
int[] st;
int n;
RSQ(int n) {
this.n = 1;
while (this.n < n) {
this.n *= 2;
}
st = new int[2 * this.n - 1];
}
// i:0-indexed
void add(int i, int x) {
i = n - 1 + i;
st[i] += x;
while (i > 0) {
i = (i - 1) / 2;
st[i] += x;
}
}
// a, b:0-indexed
// [a, b)
int query(int a, int b) {
return query(a, b, 0, 0, n);
}
private int query(int a, int b, int i, int l, int r) {
if (a >= r || b <= l) {
return 0;
}
if (a <= l && b >= r) {
return st[i];
}
return query(a, b, i * 2 + 1, l, (l + r) / 2) + query(a, b, i * 2 + 2, (l + r) / 2, r);
}
}
static class Pair implements Comparable<Pair> {
int a;
int b;
Pair(int a, int b) {
this.a = a;
this.b = b;
}
@Override
public int compareTo(Pair o) {
if (a == o.a) {
return Integer.compare(b, o.b);
}
return Integer.compare(a, o.a);
}
@Override
public int hashCode() {
return Integer.hashCode(a + b);
}
@Override
public boolean equals(Object obj) {
Pair o = (Pair) obj;
return a == o.a && b == o.b;
}
@Override
public String toString() {
// [xxx, xxxx]
StringBuilder stmp = new StringBuilder(32);
stmp.append('[');
stmp.append(a);
stmp.append(',');
stmp.append(' ');
stmp.append(b);
stmp.append(']');
return stmp.toString();
}
}
// ---------------------------------------------------
public static void main(String[] args) {
sc = new Scanner(System.in);
pr = new Printer(System.out);
solve();
pr.close();
sc.close();
}
static class Scanner {
BufferedReader br;
Scanner (InputStream in) {
br = new BufferedReader(new InputStreamReader(in));
}
private boolean isPrintable(int ch) {
return ch >= '!' && ch <= '~';
}
private boolean isCRLF(int ch) {
return ch == '\n' || ch == '\r' || ch == -1;
}
private int nextPrintable() {
try {
int ch;
while (!isPrintable(ch = br.read())) {
if (ch == -1) {
throw new NoSuchElementException();
}
}
return ch;
} catch (IOException e) {
throw new NoSuchElementException();
}
}
String next() {
try {
int ch = nextPrintable();
StringBuilder sb = new StringBuilder();
do {
sb.appendCodePoint(ch);
} while (isPrintable(ch = br.read()));
return sb.toString();
} catch (IOException e) {
throw new NoSuchElementException();
}
}
int nextInt() {
try {
// parseInt from Integer.parseInt()
boolean negative = false;
int res = 0;
int limit = -Integer.MAX_VALUE;
int radix = 10;
int fc = nextPrintable();
if (fc < '0') {
if (fc == '-') {
negative = true;
limit = Integer.MIN_VALUE;
} else if (fc != '+') {
throw new NumberFormatException();
}
fc = br.read();
}
int multmin = limit / radix;
int ch = fc;
do {
int digit = ch - '0';
if (digit < 0 || digit >= radix) {
throw new NumberFormatException();
}
if (res < multmin) {
throw new NumberFormatException();
}
res *= radix;
if (res < limit + digit) {
throw new NumberFormatException();
}
res -= digit;
} while (isPrintable(ch = br.read()));
return negative ? res : -res;
} catch (IOException e) {
throw new NoSuchElementException();
}
}
long nextLong() {
try {
// parseLong from Long.parseLong()
boolean negative = false;
long res = 0;
long limit = -Long.MAX_VALUE;
int radix = 10;
int fc = nextPrintable();
if (fc < '0') {
if (fc == '-') {
negative = true;
limit = Long.MIN_VALUE;
} else if (fc != '+') {
throw new NumberFormatException();
}
fc = br.read();
}
long multmin = limit / radix;
int ch = fc;
do {
int digit = ch - '0';
if (digit < 0 || digit >= radix) {
throw new NumberFormatException();
}
if (res < multmin) {
throw new NumberFormatException();
}
res *= radix;
if (res < limit + digit) {
throw new NumberFormatException();
}
res -= digit;
} while (isPrintable(ch = br.read()));
return negative ? res : -res;
} catch (IOException e) {
throw new NoSuchElementException();
}
}
float nextFloat() {
return Float.parseFloat(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
try {
int ch;
while (isCRLF(ch = br.read())) {
if (ch == -1) {
throw new NoSuchElementException();
}
}
StringBuilder sb = new StringBuilder();
do {
sb.appendCodePoint(ch);
} while (!isCRLF(ch = br.read()));
return sb.toString();
} catch (IOException e) {
throw new NoSuchElementException();
}
}
void close() {
try {
br.close();
} catch (IOException e) {
// throw new NoSuchElementException();
}
}
}
static class Printer extends PrintWriter {
Printer(OutputStream out) {
super(out);
}
}
}