結果

問題 No.1282 Display Elements
コンテスト
ユーザー ID 21712
提出日時 2026-05-29 14:28:29
言語 JavaScript
(node v25.8.2)
コンパイル:
true
実行:
node _filename_ ONLINE_JUDGE
結果
AC  
実行時間 323 ms / 2,000 ms
コード長 1,574 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 210 ms
コンパイル使用メモリ 6,656 KB
実行使用メモリ 92,576 KB
最終ジャッジ日時 2026-05-29 14:28:35
合計ジャッジ時間 5,624 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

/*
https://yukicoder.me/wiki/stdio#:~:text=JavaScript
上記の入力例をベース
*/

function Main(input) {

	const data = input.split("\n")
	
	const N = parseInt(data[0]);
	const A = data[1].split(" ").map( x => parseInt(x) );
	const B = data[2].split(" ").map( x => parseInt(x) );
	
	
	const btree = Node.makeTree([...A,...B]);
	
	A.sort( (a, b) => a - b );
	
	let ans = 0;
	for (let i = 0; i < N; i++) {
		btree.add(B[i]);
		ans += btree.lowerCount(A[i]);
	}
	console.log(ans);
}

class Node {
	constructor(key) {
		this.key = key;
		this.cnt = 0;
		this.lc = 0;
		this.lower = null;
		this.upper = null;
	}
	
	add(key) {
		if (this.key === key) {
			this.cnt++;
		} else if (this.key < key) {
			this.upper.add(key);
		} else if (this.key > key) {
			this.lc++;
			this.lower.add(key);
		}
	}
	
	lowerCount(key) {
		if (this.key === key) {
			return this.lc;
		} else if (this.key < key) {
			return this.lc+this.cnt+(this.upper !== null ? this.upper.lowerCount(key) : 0);
		} else if (this.key > key) {
			return this.lower !== null ? this.lower.lowerCount(key) : 0;
		}
	}
	
	static makeTree(keys) {
		keys = [...new Set(keys).keys()];
		keys.sort( (a, b) => a - b );
		return Node.build(keys, 0, keys.length-1);
	}
	
	static build(keys, i, j) {
		if (i > j) {
			return null;
		}
		if (i === j) {
			return new Node(keys[i]);
		}
		const p = (j + i) >> 1;
		const n = new Node(keys[p]);
		n.lower = Node.build(keys, i, p-1);
		n.upper = Node.build(keys, p+1, j);
		return n;
	}
}



// Don't edit this line!
Main(require("fs").readFileSync("/dev/stdin", "utf8"));
0