fork(2) download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <cstdlib>
  7. #include <vector>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11. #include <stack>
  12. #include <list>
  13. #include <cmath>
  14. #include <iomanip>
  15. #define dibs reserve
  16. #define OVER9000 1234567890
  17. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  18. #define tisic 47
  19. #define soclose 1e-8
  20. #define chocolate win
  21. // so much chocolate
  22. #define patkan 9
  23. #define ff first
  24. #define ss second
  25. #define abs(x) ((x < 0)?-(x):x)
  26. #define uint unsigned int
  27. #define dbl long double
  28. using namespace std;
  29. // mylittledoge
  30.  
  31. long long mod =1000000000;
  32.  
  33. struct fin {
  34. 	vector<long long> T;
  35. 	fin(int N) {T.resize(N+1,0);}
  36.  
  37. 	int lastone(int x) {return x&(x^(x-1));}
  38.  
  39. 	void put(int pos, long long val) {
  40. 		for(int i =pos+1; i < T.size(); i +=lastone(i)) T[i] +=val;
  41. 		}
  42.  
  43. 	long long get(int pos) {
  44. 		long long ret =0;
  45. 		for(int i =pos+1; i > 0; i -=lastone(i)) ret +=T[i];
  46. 		ret %=mod;
  47. 		if(ret < 0) ret +=mod;
  48. 		return ret;}
  49. 	};
  50.  
  51. struct info {
  52. 	int mi,mx,l;
  53.  
  54. 	bool operator<(const info &A) const {
  55. 		return mi < A.mi;}
  56. 	};
  57.  
  58. long long solve(vector<int> &A, int z, int k) {
  59. 	if(z == k) return 0;
  60. 	if(z+1 == k) return (1LL*A[z]*A[z])%mod;
  61. 	long long ret =(solve(A,z,(z+k)/2)+solve(A,(z+k)/2,k))%mod;
  62.  
  63. 	vector<info> V[2];
  64. 	int x =OVER9000, y =0, M =0;
  65. 	map<int,int> C;
  66. 	for(int i =(z+k)/2-1; i >= z; i--) {
  67. 		x =min(x,A[i]);
  68. 		y =max(y,A[i]);
  69. 		info I;
  70. 		I.mi =x, I.mx =y, I.l =(z+k)/2-i;
  71. 		C[y] =0;
  72. 		V[0].push_back(I);}
  73. 	x =OVER9000, y =0;
  74. 	for(int i =(z+k)/2; i < k; i++) {
  75. 		x =min(x,A[i]);
  76. 		y =max(y,A[i]);
  77. 		info I;
  78. 		I.mi =x, I.mx =y, I.l =i+1-(z+k)/2;
  79. 		C[y] =0;
  80. 		V[1].push_back(I);}
  81. 	// klesajuce v min
  82. 	ALL_THE(C,it) it->ss =M++;
  83.  
  84. 	fin Fp(M+tisic), Fs(M+tisic), Ft(M+tisic), Fm(M+tisic);
  85. 	int a =0;
  86. 	for(int i =0; i < V[0].size(); i++) {
  87. 		while(a < V[1].size() && V[1][a].mi >= V[0][i].mi) {
  88. 			int c =C[V[1][a].mx];
  89. 			Fp.put(c,1);
  90. 			Fs.put(c,V[1][a].l);
  91. 			Fm.put(M-c,V[1][a].mx);
  92. 			Ft.put(M-c,(1LL*V[1][a].l*V[1][a].mx)%mod);
  93. 			a++;}
  94. 		int c =C[V[0][i].mx];
  95. 		long long q =(1LL*V[0][i].mi*V[0][i].mx)%mod;
  96. 		if(q < 0) q +=mod;
  97. 		long long d =(q*V[0][i].l)%mod;
  98. 		if(d < 0) d +=mod;
  99. 		long long e =(V[0][i].mi*V[0][i].l)%mod;
  100. 		if(e < 0) e +=mod;
  101. 		ret =(ret+1LL*d*Fp.get(c))%mod;
  102. 		ret =(ret+1LL*q*Fs.get(c))%mod;
  103. 		ret =(ret+1LL*e*Fm.get(M-1-c))%mod;
  104. 		ret =(ret+1LL*V[0][i].mi*Ft.get(M-1-c))%mod;}
  105.  
  106. 	for(int i =0; i <= M+tisic; i++)
  107. 		Fp.T[i] =Ft.T[i] =Fs.T[i] =Fm.T[i] =0;
  108. 	a =0;
  109. 	for(int i =0; i < V[1].size(); i++) {
  110. 		while(a < V[0].size() && V[0][a].mi > V[1][i].mi) {
  111. 			int c =C[V[0][a].mx];
  112. 			Fp.put(c,1);
  113. 			Fs.put(c,V[0][a].l);
  114. 			Fm.put(M-c,V[0][a].mx);
  115. 			Ft.put(M-c,(1LL*V[0][a].l*V[0][a].mx)%mod);
  116. 			a++;}
  117. 		int c =C[V[1][i].mx];
  118. 		long long q =(1LL*V[1][i].mi*V[1][i].mx)%mod;
  119. 		if(q < 0) q +=mod;
  120. 		long long d =(q*V[1][i].l)%mod;
  121. 		if(d < 0) d +=mod;
  122. 		long long e =(V[1][i].mi*V[1][i].l)%mod;
  123. 		if(e < 0) e +=mod;
  124. 		ret =(ret+1LL*d*Fp.get(c))%mod;
  125. 		ret =(ret+1LL*q*Fs.get(c))%mod;
  126. 		ret =(ret+1LL*e*Fm.get(M-1-c))%mod;
  127. 		ret =(ret+1LL*V[1][i].mi*Ft.get(M-1-c))%mod;}
  128.  
  129. 	if(ret < 0) ret +=mod;
  130. 	return ret;}
  131.  
  132. int main() {
  133. 	cin.sync_with_stdio(0);
  134. 	cin.tie(0);
  135. 	int N;
  136. 	cin >> N;
  137. 	vector<int> A(N);
  138. 	for(int i =0; i < N; i++) cin >> A[i];
  139. 	cout << solve(A,0,N) << "\n";
  140. 	return 0;}
  141.  
  142. // look at my code
  143. // my code is amazing
Success #stdin #stdout 0s 3444KB
comments (?)
stdin
copy 
6
8
1
3
9
7
4
stdout
copy 
1042
https://ideone.com/p1hFJW
COCI NORMA
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!