結果

問題 No.742 にゃんにゃんにゃん　猫の挨拶
コンテスト
ユーザー ciel
提出日時 2018-10-07 11:09:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 7 ms / 2,500 ms
コード長 1,310 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 236 ms
コンパイル使用メモリ 39,808 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-12 14:09:48
合計ジャッジ時間 794 ms
ジャッジサーバーID
（参考情報） 		judge / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:34:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |         scanf("%d",&N);for(i=0;i<N;i++)scanf("%d",A+i);printf("%lld\n",merge_and_count(0,N));
      |         ~~~~~^~~~~~~~~
main.cpp:34:45: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |         scanf("%d",&N);for(i=0;i<N;i++)scanf("%d",A+i);printf("%lld\n",merge_and_count(0,N));
      |                                        ~~~~~^~~~~~~~~~

ソースコード

diff #
raw source code 

#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
int A[999999], W[999999];
long long merge_and_count(int l, int r) { // range [l,r)
	if (l+1 >= r) return 0; // empty
	if (l+2 == r) { // [l,r) == [l,l+1] 要素2つだけ
		if (A[l] <= A[l+1]) return 0; // 逆転はなし
		std::swap(A[l], A[l+1]);
		return 1; // 逆転一つ
	}
	int m = (l+r)/2; // [l,r) == [l,m) + [m,r)
	long long cl = merge_and_count(l, m); // 左半分を再帰的に数える
	long long cr = merge_and_count(m, r); // 右半分を再帰的に数える
	long long c = 0; // 左と右を混ぜるときの逆転数
	int i=l, j=m; // iは[l,m)を動き, jは[m,r)を動いて、
	int k=l; // 小さいものから W[k] に書き込む
	while (i<m && j<r) { // A[i]とA[j]を比べながら進む
		if (A[i] <= A[j]) W[k++] = A[i++]; // 左半分の方が小さく逆転なし
		else {
			W[k++] = A[j++];
			c += m-i; // 左半分の方が大きい、左半分で未処理の要素だけ飛び越える
		}
	}
	while (i<m) W[k++] = A[i++]; // 左半分が余った場合
	while (j<r) W[k++] = A[j++]; // 右半分が余った場合
	//assert(k == r);
	std::copy(W+l, W+r, A+l);
	return cl + cr + c;
}
int main(){
	int T,i,N;
	scanf("%d",&N);for(i=0;i<N;i++)scanf("%d",A+i);printf("%lld\n",merge_and_count(0,N));
}
0