結果

問題 No.121 傾向と対策：門松列（その２）
コンテスト
ユーザー koyumeishi
提出日時 2015-01-09 01:24:46
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 666 ms / 5,000 ms
コード長 2,326 bytes
コンパイル時間 937 ms
コンパイル使用メモリ 88,188 KB
実行使用メモリ 28,592 KB
最終ジャッジ日時 2024-06-28 18:32:43
合計ジャッジ時間 5,729 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

class BinaryIndexedTree_1_indexed{
	void init(const vector<int> &A){
		for(int i=0; i<N; i++){
			add(i+1, A[i]);
		}
	}
	
public:
	vector<int> T;
	int N;
	
	BinaryIndexedTree_1_indexed(const int n) : T(n+1,0), N(n){
		
	}
	
	BinaryIndexedTree_1_indexed(const vector<int> &A) : T(A.size()+1,0), N(A.size()){
		init(A);
	}

	//caution : position "i" must be 1-indexed
	void add(int i, const int x){
		while(i <= N){
			T[i] += x;
			i += i & -i;
		}
	}

	//get sums [0,i]
	int get_sum(int i){
		int ret=0;
		while(i>0){
			ret += T[i];
			i -= i & -i;
		}
		return ret;
	}
};


int main(){
	int N;
	cin >> N;
	vector<int> L(N);
	for(int i=0; i<N; i++) cin >> L[i];
	
	vector<pair<int,int> > v(N);
	for(int i=0; i<N; i++){
		v[i] = {L[i], i+1};
	}
	sort(v.begin(), v.end());
	
	long long ans = 0;
	
	//smaller
	{
		BinaryIndexedTree_1_indexed BIT(N);
		queue<int> pool;
		int last = -1;
		for(int i=0; i<N; i++){
			if(last == v[i].first){
				pool.push(v[i].second);
			}else{
				last = v[i].first;
				while(!pool.empty()){
					BIT.add(pool.front(), 1);
					pool.pop();
				}
				pool.push(v[i].second);
			}
			long long left = BIT.get_sum(v[i].second);
			long long right = BIT.get_sum(N) - left;
			ans += left*right;
			
		}
	}

	//greater
	{
		BinaryIndexedTree_1_indexed BIT(N);
		queue<int> pool;
		int last = -1;
		for(int i=N-1; i>=0; i--){
			if(last == v[i].first){
				pool.push(v[i].second);
			}else{
				last = v[i].first;
				while(!pool.empty()){
					BIT.add(pool.front(), 1);
					pool.pop();
				}
				pool.push(v[i].second);
			}
			long long left = BIT.get_sum(v[i].second);
			long long right = BIT.get_sum(N) - left;
			ans += left*right;
		}
	}

	v.push_back( {1000000000+10, 1000000+10});
	vector<int> same;
	int last = -1;
	for(int i=0; i<=N; i++){
		if(last == v[i].first){
			same.push_back(v[i].second);
		}else{
			int cnt = same.size();
			for(int j=1; j<cnt; j++){
				int left = j;
				int right = cnt-j;
				int med = same[j] - same[j-1] - 1;

				ans -= 1LL*left*right*med;
			}

			same = vector<int>();
			same.push_back(v[i].second);
			last = v[i].first;
		}
	}

	cout << ans << endl;
	return 0;
}
0