結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
![]() |
提出日時 | 2020-07-17 21:51:04 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 138 ms / 2,000 ms |
コード長 | 4,515 bytes |
コンパイル時間 | 2,408 ms |
コンパイル使用メモリ | 109,440 KB |
実行使用メモリ | 37,120 KB |
最終ジャッジ日時 | 2024-11-29 23:18:34 |
合計ジャッジ時間 | 6,303 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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;using System.Collections.Generic;using CompLib.Collections;using CompLib.Collections.Generic;using CompLib.Util;public class Program{// private int N;public void Solve(){var sc = new Scanner();int n = sc.NextInt();int[] a = sc.IntArray();int[] b = sc.IntArray();int[] indexOf = new int[n + 1];for (int i = 0; i < n; i++){indexOf[b[i]] = i;}int[] tmp = new int[n];for (int i = 0; i < n; i++){tmp[i] = indexOf[a[i]];}long ans = 0;var st = new SegmentTree<int>(n, (l, r) => l + r, 0);for (int i = 0; i < n; i++){ans += st.Query(tmp[i], n);st[tmp[i]]++;}Console.WriteLine(ans);}public static void Main(string[] args) => new Program().Solve();}namespace CompLib.Collections.Generic{using System;public class SegmentTree<T>{private readonly int N;private T[] _array;private T _identity;private Func<T, T, T> _operation;public SegmentTree(int size, Func<T, T, T> operation, T identity){N = 1;while (N < size) N *= 2;_identity = identity;_operation = operation;_array = new T[N * 2];for (int i = 1; i < N * 2; i++){_array[i] = _identity;}}/// <summary>/// A[i]をnに更新 O(log N)/// </summary>/// <param name="i"></param>/// <param name="n"></param>public void Update(int i, T n){i += N;_array[i] = n;while (i > 1){i /= 2;_array[i] = _operation(_array[i * 2], _array[i * 2 + 1]);}}private T Query(int left, int right, int k, int l, int r){if (r <= left || right <= l){return _identity;}if (left <= l && r <= right){return _array[k];}return _operation(Query(left, right, k * 2, l, (l + r) / 2),Query(left, right, k * 2 + 1, (l + r) / 2, r));}/// <summary>/// A[left] op A[left+1] ... op A[right-1]を求める/// </summary>/// <param name="left"></param>/// <param name="right"></param>/// <returns></returns>public T Query(int left, int right){return Query(left, right, 1, 0, N);}public T this[int i]{set { Update(i, value); }get { return _array[i + N]; }}}}namespace CompLib.Util{using System;using System.Linq;class Scanner{private string[] _line;private int _index;private const char Separator = ' ';public Scanner(){_line = new string[0];_index = 0;}public string Next(){if (_index >= _line.Length){string s;do{s = Console.ReadLine();} while (s.Length == 0);_line = s.Split(Separator);_index = 0;}return _line[_index++];}public string ReadLine(){_index = _line.Length;return Console.ReadLine();}public int NextInt() => int.Parse(Next());public long NextLong() => long.Parse(Next());public double NextDouble() => double.Parse(Next());public decimal NextDecimal() => decimal.Parse(Next());public char NextChar() => Next()[0];public char[] NextCharArray() => Next().ToCharArray();public string[] Array(){string s = Console.ReadLine();_line = s.Length == 0 ? new string[0] : s.Split(Separator);_index = _line.Length;return _line;}public int[] IntArray() => Array().Select(int.Parse).ToArray();public long[] LongArray() => Array().Select(long.Parse).ToArray();public double[] DoubleArray() => Array().Select(double.Parse).ToArray();public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();}}