fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <map>
  5. using namespace std;
  6.  
  7. const int MOD = 1e9 + 7;
  8. int main() {
  9. 	cin.tie(0);
  10. 	ios_base::sync_with_stdio(0);
  11.  
  12. 	int n;
  13. 	cin >> n;
  14. 	vector<int> x(n);
  15. 	set<int> x_set;
  16. 	map<int, int> x_map_idx;
  17.  
  18. 	for(int &val: x){
  19. 		cin >> val;
  20. 		x_set.insert(val);
  21. 	}
  22. 	for(int val: x_set){
  23. 		x_map_idx[val] = x_map_idx.size() + 1;
  24. 	}
  25. 	for(int &val: x){
  26. 		val = x_map_idx[val];
  27. 	}
  28.  
  29. 	vector<int> BITS(n + 1);
  30. 	auto update = [&](int pos, int val){
  31. 		while(pos < BITS.size()){
  32. 			BITS[pos] = (BITS[pos] + val) % MOD;
  33. 			pos += pos & -pos;
  34. 		}
  35. 	};
  36.  
  37. 	auto query = [&](int pos){
  38. 		int ans = 0;
  39. 		while(pos){
  40. 			ans = (ans + BITS[pos]) % MOD;
  41. 			pos -= pos & -pos;
  42. 		}
  43. 		return ans;
  44. 	};
  45.  
  46. 	int ans = 0;
  47. 	for(auto &val: x){
  48. 		int end_with_val_cnt = query(val - 1) + 1;
  49. 		ans = (ans + end_with_val_cnt) % MOD;
  50. 		update(val, end_with_val_cnt);
  51. 	}
  52.  
  53. 	cout << ans << '\n';
  54. 	return 0;
  55. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
3
2 1 3
stdout
copy 
5
https://ideone.com/fzdTJj
language:
C++ (gcc 8.3)
created:
1 hour ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!