fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define FNAME "test"
  6.  
  7. const int N = 2e5 + 5;
  8. const int M = 998244353;
  9. const int modinv2 = (M + 1) / 2;
  10.  
  11. int n, m;
  12. pair<int,int> booth[N];
  13. int last[N];
  14. int ans;
  15.  
  16. void Task() {
  17. 	ios_base::sync_with_stdio(false);
  18. 	cin.tie(0); cout.tie(0);
  19. 	cout << fixed << setprecision(9);
  20. 	if (fopen(FNAME".inp","r")) {
  21. 		freopen(FNAME".inp","r",stdin);
  22. 		freopen(FNAME".out","w",stdout);
  23. 	}
  24. }
  25.  
  26. void compress() {
  27. 	set<int> s;
  28. 	for (int i = 1; i <= n; i++) s.insert(booth[i].first);
  29. 	vector<int> b(s.begin(), s.end());
  30. 	for (int i = 1; i <= n; i++) booth[i].second = lower_bound(b.begin(), b.end(), booth[i].first) - b.begin() + 1;
  31. }
  32.  
  33. void Input() {
  34. 	cin >> n >> m;
  35. 	for (int i = 1; i <= n; i++) cin >> booth[i].first;
  36. 	compress();
  37. }
  38.  
  39. int cnt(int n) {
  40. 	return ((1LL * n * (n + 1) % M) * modinv2) % M;
  41. }
  42.  
  43. void solve() {
  44. 	memset(last, 0, sizeof(last));
  45. 	ans = 0;
  46. 	int sum = (1LL * ((1LL * m * (m + 1)) % M) * modinv2) % M;
  47. 	for (int i = 1; i <= n; i++) {
  48. 		if (last[booth[i].second] == 0) sum = (sum + M - booth[i].first) % M;
  49. 		int l = last[booth[i].second] + 1, r = i - 1;
  50. 		if (l <= r) ans = (ans + ((1LL * cnt(r - l + 1) * booth[i].first) % M)) % M;
  51. 		last[booth[i].second] = i;
  52. 	}
  53. 	for (int i = 1; i <= n; i++) {
  54. 		if (last[booth[i].second] != 0) {
  55. 			int l = last[booth[i].second] + 1, r = n;
  56. 			if (l <= r) ans = (ans + ((1LL * cnt(r - l + 1) * booth[i].first) % M)) % M;
  57. 			last[booth[i].second] = 0;
  58. 		}
  59. 	}
  60. 	int tmp = cnt(n);
  61. 	sum = (1LL * sum * tmp) % M;
  62. 	ans = (ans + sum) % M;
  63. 	cout << ans << '\n';
  64. }
  65.  
  66. void Solve() {
  67. 	//Your Code
  68. 	Input();
  69. 	solve();
  70. }
  71.  
  72. int main() {
  73. 	Task();
  74. 	Solve();
  75. 	cerr << "\nTime run: " << 1000*clock()/CLOCKS_PER_SEC << "ms";
  76. 	return 37^37;
  77. }
Success #stdin #stdout #stderr 0s 5284KB
comments (?)
stdin
copy 
8 4
2 3 1 2 4 3 1 3
stdout
copy 
124
stderr
copy 
Time run: 4ms
https://ideone.com/O5k7Lk
language:
C++ (gcc 8.3)
created:
2 days 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!