結果

提出番号	1853
提出者	ecasdqina
言語	C++
提出日時	2018-08-04 14:14:19
問題名	(71)音楽ゲーム
結果	WA
点数	0%

---

テストケース

ソースコード

#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

struct SegmentTree {
	std::vector<i64> seg;
	int sz = 1;
	
	SegmentTree(int n) {
		while(sz < n) sz *= 2;
		seg.assign(sz * 2 - 1, 0);
	}
	
	void add(int k) {
		k += sz - 1;
		seg[k] += 1;
		
		while(k) {
			k = (k - 1) / 2;
			
			seg[k] = seg[2 * k + 1] + seg[2 * k + 2];
		}
	}
	
	i64 get(int a, int b, int k, int l, int r) {
		if(r<=a||b<=l) return 0;
		if(a<=l&&r<=b) return seg[k];
		
		return get(a, b, 2 * k + 1, l, (l + r) / 2) + get(a, b, 2 * k + 2, (l + r) / 2, r);
	}
	
	i64 get(int a, int b) {
		return get(a, b, 0, 0, sz);
	}
};

int main(){
	int n; cin >> n;
	SegmentTree	seg(100010);
	
	i64 ans = 1;
	for(int i = 0; i < n; i++) {
		int a; cin >> a;
		
		seg.add(a);
		ans += seg.get(0, a);
		ans %= i64(1e9 + 7);
	}
	
	cout << ans << endl;
	return 0;
}