結果
問題 | No.742 にゃんにゃんにゃん 猫の挨拶 |
ユーザー |
|
提出日時 | 2018-10-05 22:50:14 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 443 ms / 2,500 ms |
コード長 | 2,230 bytes |
コンパイル時間 | 2,850 ms |
コンパイル使用メモリ | 79,232 KB |
実行使用メモリ | 48,896 KB |
最終ジャッジ日時 | 2024-10-12 13:58:16 |
合計ジャッジ時間 | 5,869 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
import java.io.FileNotFoundException;import java.io.PrintWriter;import java.util.ArrayList;import java.util.Arrays;import java.util.Scanner;class Main {class BIT {int n;long[] v;public BIT(int n_) {n = n_;v = new long[n + 1];}void add(int k, int val) {while (k <= n) {v[k] += val;k += k & -k;}}long sum(int k) {long ret = 0;while (k >= 1) {ret += v[k];k -= k & -k;}return ret;}long sum(int l, int r) {return sum(r - 1) - sum(l - 1);}}void run() {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int[] M = new int[N];SegmentTree seg1 = new SegmentTree(N);SegmentTree seg2 = new SegmentTree(N);SegmentTree seg3 = new SegmentTree(N);long ans = 0;for (int i = 0; i < N; ++i) {M[i] = sc.nextInt();--M[i];if (i < M[i]) {// 同じ方向ans += seg1.query(M[i], N);seg1.add(M[i]);} else if (i > M[i]) {// 同じ方向ans += seg2.query(M[i], i + 1);// 内側方向ans += seg1.query(M[i], N);seg2.add(M[i]);} elseseg3.add(M[i]);}// 動かない猫との挨拶をカウントfor (int i = 0; i < N; ++i) {if (i != M[i]) {ans += seg3.query(Math.min(i, M[i]), Math.max(i, M[i]) + 1);} else {ans += seg3.query(i, i + 1) - 1;}}PrintWriter pw = new PrintWriter(System.out);pw.println(ans);pw.close();}class SegmentTree {int n;int[] sum;public SegmentTree(int n_) {n = 1;while (n < n_) {n *= 2;}sum = new int[2 * n - 1];}void add(int k) {k += n - 1;++sum[k];while (k > 0) {k = (k - 1) / 2;sum[k] = sum[2 * k + 1] + sum[2 * k + 2];}}int query(int a, int b) {return query(0, n, a, b, 0);}int query(int l, int r, int a, int b, int k) {if (r <= a || b <= l)return 0;else if (a <= l && r <= b)return sum[k];else {return query(l, (l + r) / 2, a, b, 2 * k + 1) + query((l + r) / 2, r, a, b, 2 * k + 2);}}}void tr(Object... objects) {System.out.println(Arrays.deepToString(objects));}public static void main(String[] args) throws FileNotFoundException {new Main().run();}}