結果
問題 |
No.1115 二つの数列 / Two Sequences
|
ユーザー |
![]() |
提出日時 | 2021-05-03 18:38:03 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 100 ms / 2,000 ms |
コード長 | 1,363 bytes |
コンパイル時間 | 912 ms |
コンパイル使用メモリ | 116,652 KB |
実行使用メモリ | 35,456 KB |
最終ジャッジ日時 | 2024-07-22 09:24:47 |
合計ジャッジ時間 | 5,377 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 35 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; public class BIT { private int[] data; private int n; public BIT(int n) { this.n = n; data = new int[n + 1]; } public int getSum(int i) { var s = 0; while (i > 0) { s += data[i]; i -= i & -i; } return s; } public void addix(int i, int x) { while (i <= n) { data[i] += x; i += i & -i; } } } public class hello { static void Main() { var n = int.Parse(Console.ReadLine().Trim()); string[] line = Console.ReadLine().Trim().Split(' '); var a = Array.ConvertAll(line, int.Parse); line = Console.ReadLine().Trim().Split(' '); var b = Array.ConvertAll(line, int.Parse); getAns(n, a, b); } static void getAns(int n, int[] a, int[] b) { var rb = new int[n + 1]; for (int i = 0; i < n; i++) rb[b[i]] = i + 1; var c = new int[n]; for (int i = 0; i < n; i++) c[i] = rb[a[i]]; getINV(n, c); } static void getINV(int n, int[] a) { var bit = new BIT(n); var ans = 0L; for (int i = 0; i < n; i++) { bit.addix(a[i], 1); if (i >= 1) ans += i + 1 - bit.getSum(a[i]); } Console.WriteLine(ans); } }