結果

問題 No.1282 Display Elements
コンテスト
ユーザー ID 21712
提出日時 2026-05-29 17:23:36
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
RE  
実行時間 -
コード長 2,387 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 13,238 ms
コンパイル使用メモリ 276,892 KB
実行使用メモリ 12,544 KB
最終ジャッジ日時 2026-05-29 17:23:57
合計ジャッジ時間 16,221 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15 RE * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/*
解説ページにリンクのあったc-yanさんによるユーザ解説にあった手法

B[i]を逐次追加してソートして二分探索する
ソートして二分探索する配列を2つに分ける
短い配列と長い配列とに

短い配列のほうにB[i]を挿入してはソート
短い配列と長い配列をA[i]で二分探索して個数を数える
短い配列がいっぱいになったら
長い配列に全部挿入して、長い配列をソート、短い配列を空にする

短い配列の長さを M とするなら
短い配列のソートを N 回実行するので
時間計算量は O( N * M * log(M) )
長い配列のソートは N/M 回実行されるので
時間計算量は O( N/M * N * log(N) )
Mをうまくとるなら M = sqrt(N) とすると
どちらのソートも計算量は O( sqrt(N) * N * log(N) ) になる
今回の問題の N の最大値と実行制限時間においては間に合うらしい


これ
O( sqrt(N) * N * log(N) ) が間に合うのなら
累積和を平方分割管理で処理しても間に合うのでは？

平方分割は間に合わないと思って除外して考えてたけど
試してみよう

*/
package main

import . "fmt"
import . "os"
import bf "bufio"
import . "slices"
import "math"

func main() {
	rd := bf.NewReader(Stdin)
	
	var n int
	Fscan(rd, &n)
	a := make([]int, n)
	for i := range a {
		Fscan(rd, &a[i])
	}
	b := make([]int, n)
	for i := range b {
		Fscan(rd, &b[i])
	}

	// 座標圧縮	
	// 今回は値そのものは答えに使用しないためインデックスに置き換えるだけ
	keys := Concat(a, b)
	Sort(keys)
	keys = Compact(keys)
	table := make(map[int]int)
	for i, k := range keys {
		table[k] = i
	}
	for i, k := range a {
		a[i] = table[k]
	}
	for i, k := range b {
		b[i] = table[k]
	}
	
	Sort(a)
	
	rootN := int(math.Ceil(math.Sqrt(float64(n))))
	rootN = max(rootN, (n+rootN-1)/rootN)
	rootN = max(rootN, (n+rootN-1)/rootN)
	
	arr1 := make([]int, rootN+1)
	arr2 := make([][]int, rootN+1)
	for i := range arr2 {
		arr2[i] = make([]int, rootN+1)
	}
	
	ans := 0
	for i := 0; i < n; i++ {
		p1 := b[i] / rootN
		for j := p1+1; j < len(arr1); j++ {
			arr1[j]++
		}
		p2 := b[i] % rootN
		for j := p2+1; j < len(arr2[p1]); j++ {
			arr2[p1][j]++
		}
		q1 := a[i] / rootN
		ans += arr1[q1]
		q2 := a[i] % rootN
		ans += arr2[q1][q2]
	}
	Println(ans)
}
0