結果

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

---

テストケース

ソースコード

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

i64 mod_pow(long long x, long long n, const int mod) {
	i64 ret = 1;
	
	while(n) {
		if(n & 1) (ret *= x) %= mod;
		
		(x *= x) %= mod;
		n >>= 1;	
	}
		
	return ret;
}


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, int x) {
		k += sz - 1;
		seg[k] += x;
		seg[k] %= (i64)(1e9 + 7);
		
		while(k) {
			k = (k - 1) / 2;
			
			seg[k] = (seg[2 * k + 1] + seg[2 * k + 2]) % (i64)(1e9 + 7);
		}
	}
	
	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)(1e9 + 7);
	}
	
	i64 get(int a, int b) {
		return get(a, b, 0, 0, sz);
	}
};

int main(){
	int n; cin >> n;
	std::map<int, int> mp;
	for(int i = 0; i < n; i++) {
		int a; cin >> a;
		mp[a] += 1;
	}
	
	SegmentTree seg(100010); seg.add(1, 1);
	for(auto p : mp) {
		i64 A = seg.get(1, p.first);
		i64 B = mod_pow(2, p.second - 1, (i64)(1e9 + 7));
		
		seg.add(p.first, A * p.second);
	}	
	
	cout << seg.get(1, 100010) << endl;
	return 0;
}